第一节布尔函数的表示非线性组合函数也称为逻辑函数或布尔函数(boolean function)。

研究布尔函数的密码学性质已成为序列密码、HASH 函数和分组密码设计与分析的关键所在。

目前，关于布尔函数的密码学的性质的研究主要包括以下几个方面：•非线性次数；•非线性度（相关度）；•线性结构；•退化性；•相关免疫性(correlation immunity)；•严格雪崩准则(strict avalanche criterion)•扩散准则(propagation criterion)；•代数免疫性通常，布尔函数的以上密码学性质是相互关联的。

本章主要研究布尔函数的表示方法、重量与概率计算、非线性度和相关免疫性。

布尔函数的定义定义3.1 一个n 元布尔函数f (x ) = f (x 1, x 2, …, x n )是2n F 到2F 的一个映射。

由于2n F 含2n个元素, 故2n F 上的布尔函数共有22n个。

真值表表示：每个二元n维向量为(an-1, an-2, …, a)一个真值指派。

规定种可能的2n真值指派是按照它们表示的二进制数的大小排列的。

布尔函数的表示方法即对真值指派120(,,......,)−−n n a a a 和120(,,......,)−−n n b b b ,如果有1122−−==<∑∑n n i jiji j a b , 则120(,,......,)−−n n a a a 排在120(,,......,)−−n n b b b 之前。

称120(,,......,)n n f a a a −−为f (x )在真值指派120(,,......,)n n a a a −−下的函数值。

于是f (x )的真值表由2n F 中所有真值指派及其函数值构成。

下表是一个二元布尔函数的真值表。

1x 2x ),(21x x f 0 0 1 0 111 0 1 1 1任意两个n 元布尔函数f (x )和g (x )相等当且仅当它们在2n F 的每个真值指派下都有相同的函数值, 此时, 记作f (x ) = g (x ), 否则就说它们是不同的n 元布尔函数, 记作f (x ) ≠ g (x )。

考虑最简单的n 元布尔函数, 它只在2nF 的一个真值指派下取值为1, 在其它真值指派下均取值为0。

设取值为1的真值指派是120(,,......,)n n a a a −−, 因此, n 元布尔函数11220()(1)(1)......(1)n n n f x x a x a x a −−=++++++•小项表示：若我们规定1i i x x =, 01ii i x x x =+=, i = 1, 2, …, n 。

则1i n i x a −++ = n ia ix−, 从而在2n F中真值指派120(,,......,)n n a a a −−下取值为1, 而在其它真值指派下均取值为0的函数f (x )就可以记为12012()......n n a a a nf x x xx −−=。

称n 元布尔函数12012()......n n a a a nf x x xx −−=为一个n 元小项函数。

设f (x )是任意一个n 元布尔函数。

12012012012(,,.......,)()(,,......,)......n n n n a a a n n na a a f x f a a a xxx−−−−−−=∑称上面的表达式为n 元布尔函数的小项表示。

f(x)的小项表示由它的真值表唯一确定, 故f(x)的小项表示是唯一的。

f(x)是它取值为1的那些真值指派对应的小相函数之和。

例3.1 下表中二元布尔函数的小项表示为:000110121212()f x x x x x x x =++1x 2x ),(21x x f 0 0 1 0 111 0 1 1 1如果把f(x)的小项表示中每一个小项函数展成x1, x2, …, xn的多项式, 那么我们可以得到f(x)的多项式表示。

•多项式表示：121212012 (121)......01......()....................r rr ni i ij i j n ni i jni i i i i i r i i i nf x c c x c x x c x x x c x x x =<=≤<<≤=++++=∑∑∑∑，其中12......r i i i c = 0或1。

注:当r = 0时, 我们约定12......r i i i x x x = 1。

•由于f(x)的小项表示是唯一的, f(x)的多项式表示也是唯一的。

•f(x)多项式表示中, 每一个积12......ri i ix x x称为一个单项, c0称为常数项。

如果c0= 1, 称f(x)为反转多项式; 如果c0= 0, 称f(x)为规范多项式。

我们称含有最多变元的单项为最高次项，并称最高次项中变元的个数为布尔函数f(x)的次数, 记为deg(f)。

当deg(f) = 1时, 称f(x)为线性布尔函数;当deg(f) ≥2时, 称f(x)为非线性布尔函数。

写出下面三元布尔函数的小项表示和多项式表示x1x2x3 f (x1, x2, x3)0 0 0 10 0 1 00 1 0 10 1 1 01 0 0 01 0 1 01 1 0 11 1 1 0f(x) =x1x2x3+x1x2+x1x3+x1+x3+ 1如果把多项式表示中单项式12......r i i i x x x 改写成如下形式1212()......n k k k k nR x x x x =式中, k 是(k 1, k 2, …, k n )的二进制表示, 0 ≤ k ≤ 2n− 1, k =12nn ii i k −=∑并约定11,0====⎧⎪⎨⎪⎩iik ii i ki i x x k x k ,当当 •Reed －Muller 谱表示：将与单项式1212......n k k k nx x x 相应的系数记为()f k , 则f (x )可以改写成210()()()−==∑nk k f x f k R x ,这就是f (x )的Reed-Muller 展开式, 通常按k 递增的方式书写112()(0)(1)(2)......(21)......−=++++− nn n n f x f f x f x f x x x记((0),(1),......,(21))=− nf f f f , 则称f 为f (x )的Reed-Muller 谱表示实际上f是布尔函数f (x )的多项式表示中系数的一个新的排列。

例3.1中布尔函数的多项式表示和Reed-muller 谱表示分别为:12121212()(1)(1)(1)(1)1f x x x x x x x x x =++++++=+(1,0,0,1)f =定义3.2 递归地定义2F 上矩阵0(1)A =，111111001n n n n n A A A A A −−−−⎛⎞⎛⎞=⊗=⎜⎟⎜⎟⎝⎠⎝⎠这里⊗表示矩阵的Keronecker 积。

用数学归纳法可以证明:2nn A I =(这里n I 是22n n×的单位矩阵)。

我们有如下关系：((0),(1),......,(21))()nn n f f f f A f x A ∆=−= 其逆变换为2()()((0),(1),......,(21))nnn n f x f x A fA f f f A ===−(Reed-Muller 谱表示)快速计算f (x )的Reed-muller 谱的一个方法 设1()f x 和2()f x 分别表示f (x )真值表的前一半值和后一半值, 则112111((),()())n n n f f x A f x A f x A −−−=+按此规则一直迭代到0A 就得到f (x )的Reed-muller 谱。

如f 1(x ) A n −1 = ( f 11(x ) A n −2 , f 11(x ) A n −2 + f 12(x ) A n −2)定义3.3 设x = (x 1, ……, x n )， w = (w 1, ……, w n ) ∈2n F , x 和w 的点积定义为w ⋅x = w 1x 1 + w 2x 2 +…… + w n x n (mod 2)。

称()()()2112⋅∈=⋅−∑nw xf nx F S w f x ,()()()()2211,2+⋅∈=−∈∑nf x w xn f n x F S w w F分别为f (x )的Walsh 线性谱和Walsh 循环谱。

•Walsh 谱表示：布尔函数的Walsh 谱表示(反演公式)()()()221,nw xn f w F f x S w x F ⋅∈=⋅−∈∑()()()()221,nw xn fw F f x S w x F ⋅∈=⋅−∈∑其中S f (w )和S ( f )(w )分别为f (x )在w 处的Walsh 线性谱和Walsh 循环谱。

f (x )的Walsh 变换具有下列性质: (1) 初值定理(0)2()nf H S W f −=， 2(0)()nfw F f Sw ∈=∑,其中()H W f 是f (x )的Hamming 重量。

证明: 由定义易得。

(2) 位移定理: 设2n c F ∈, 对任意给定的2n x F ∈及2n F 上的实值函数f (x ), g (x ) = f (x + c) 当且仅当对所有的w 2n F ∈, 有()(1)()cwg f S w S w =−证明: “⇒” 令''''121212(,,......,)(,,......,)(,,......,)nn n x x x x x x x c c c x c ==+=+,则当x 跑遍2n F 时, 也跑遍2n F 。

于是2''2''2'()'()2()(1)2()(1)(1)2()(1)(1)()n nnn wxg x F nw x c x F wcnx wx F wcf S w f x c f x f x S w −∈−+∈−∈=+−=−=−−=−∑∑∑反之,2()()(1)nwxgw F g x Sw ∈=−∑22()(1)()(1)()(1)()nncwwxf w F w x c fw F S w Sw f x c ∈+∈=−−=−=+∑∑(3) 巴塞代尔定理:2222()2()nnnfw F x F S w f x −∈∈=∑∑证明:22222222()()2()(1)2()()(1)2()nnn nnnnwxffw F w F x F nwxnf x F w F x F Sw Sw f x f x S w f x −∈∈∈−−∈∈∈=⋅−=−=∑∑∑∑∑∑(4) 守恒定理:2(){0,1}n fw F S w∈∈∑,22()(0)n f fw F S w S∈=∑定义3.4 两个定义在2n F 上的实值函数f (x ), g (x )的卷积f ·g 定义为2n F 上的实值函数h (x ): 对任意2n x F ∈, h (x )定义为下面的积:2()2()()nnc F h x f x c g c −∈=+∑(5) 卷积定理: 对实值函数f (x ), g (x )和h (x ), 有 2()2()()nn c F h x f x c g c −∈=+∑当且仅当()()()h f g S w S w S w =证明:2()2()(1)nnwxh x F S w h x −∈=−∑222(2()())(1)nnnn wxx F c F f x c g c −−∈∈=+−∑∑''22'()22()()(1)nnnnw x c c F x F f x g c −−+∈∈=−∑∑''22'2()(1)2()(1)()()nnnwcnwx c F x F g f g c f x S w S w −−∈∈=−−=∑∑充分性的证明与上类似。