（完整版）布尔函数参考答案.doc

本word文档可编辑可修改 湖北大 学研究生课程考试参考答案及评分标准课程编号0701E0205课程名称密码与编码 学中 的布尔函数注：需写清题号、每小题分值、参考答案要点、评分标准等一、概念题参考答案及评分标准：nn到1.设n是nF是二元有限域，为正整数， F2F上 的维向量空间，从 F2F 的映222射： f : F2nF称为 n元布尔函数 .2一个 n元布尔函数 f可以表示为 F上 的含 n个变元 的多项式 :2f (x ,x , xn)f (a ,a , a )(x a 1)( x a 1) (x a 1)1 2 n 1 1 2 2 n n12a F2iax2a2 xnanf (a ,a , a )x1 .112na F2in这里xi a 1表示 F中 的加法运算，即模 2 的加法运算 .形如上式 的表示称i 2i 1为布尔函数 f 的小项表示 .若将小项表示展开并合并同类项，则会得到如下形式 的一个多项式：nf (x , x , x ) a0a xiia x x jai1 xi1 xid,i da x xn1, n 112ni , jii 11 i j n1 ij n这里系数 ai ,F2.j评分标准：答出 n元布尔函数 的定义得 5分，答出其多项式表示得 5分.2布尔函数 的安全性指标主要有：平衡性、代数次数、差分均匀度、非线性度、相关免疫阶、弹性阶和代数免疫度等等 .平衡性：一个 n元布尔函数是平衡 的，当且仅当其真值表中 0和 1 的个数相同，也就是该布尔函数 的 Hamming重量为 2n 1 .代数次数：密码体制中使用 的布尔函数通常具有高 的代数次数.差分均匀度：设是一个 n元布尔函数，其差分均匀度定义为关注我 实时更新 最新资料 n2max max { x F | f ( x a) f ( x)} .fnF20 a F2非线性度： f 的非线性度 NL ( f )定义为 f和所有仿射函数 的最小 Hamming距离：NL( f ) min d( f ,l) min wt( f l ).l Anl An相关免疫阶：设是一个 n元布尔函数，其中是上独立且均匀分布 的随机变量，如果与中任意个变元统计独立，则称是 m阶相关免疫函数。

评分标准：每个指标 2分，答出其中 5个得 10分.3.（10分）设 m 1， n 2mn2，0 r m.线性空间 F中 的子集合nRM (r ,m) {c F | f B ,deg f r}f2m叫做 r阶 的二元 Reed-Muller码其中 B为全体布尔函数 的集合m二、证明题答题要点及评分标准：1.（1）（10分）根据循环 Walsh谱 的定义 ,得到W ( )f( 1)f ( x) xgx F2nnn{ x F | f (x) xg } { x F | f ( x) xg }22n2 2 t( fgx)（2）（10分）根据循环 Walsh谱 的定义 ,得到2( 1)f ( x) xg( 1) f ( y ) ygW ( )fF2nF2n x F2ny F2n( 1) f ( x)f ( y)( 1) g(x y)x F2n y F2nF2nn2 22nx y F2ngxn倒数第二个等号成立是因为( 1)仅当 x 0时取值 2，其他时候取值均为F2n0. %2.证明：定义 f (x) 的对偶函数 f (x)如下：n20, Wf x2;%f xn21, Wf x2,n%运用 Walsh变换 的性质得出 W a%f22，即 f x也是 Bent函数.（4分）再证明 n元布尔函数 f (x)是 Bent函数当且仅当矩阵nBfh u,v[2 W u v ]2fu,v F2nu,v F2nnn是一个 2 2 的 Hadamard矩阵.（6分）最后证明原命题：%（必要性） f (x)是 Bent函数则 f (x)也是 Bent函数.nu v1 ，得出矩阵通过 22W u v%fn2f u vHh u,v[ 1][2W u v ] u v F2n B f%u,v F2nu v F2n,f%,是 Hadamard矩阵；（5分）f x y（充分性）由 Hh x, y[ 1]x y F2n.,u,v F2n得出f x f x yn12 yx F2nn2y u2n将上式两边同时乘以1，并对 y求和得到 W u 2即W u2，则 f (x)ff是 Bent函数.（5分）3.证明：先利用 McEliece定理，证明若 f (x)是相关免疫函数， m n 1，则n m 1m 1W a 0 mod2dn2,对任意 a F .（5分）f于是max W a2m 1fna F21再结合 NL( f ) 2n 1max W a即得f2na F2n 1mNL( f ) 22 .（5分） 类似 的，若 f (x)是 m阶弹性函数n m 2dm 2W a 0 mod2n2，对任意 a F .（5分）f1再结合 NL( f ) 2n 1max W a即得f2na F2n 1m 1NL ( f ) 22 .（5分）n4.证明：记 T为所有代数次数不超过 的 n元单项式构成 的集合；2令TffX | X T,则n2nin2，（5分）T Tf 2i注意到 T中所有元素线性无关，从而a XXa fY 0，YX TY T其中 a， aY F ,且存在某个 aY 0.令X2ha X， gXa Y，YX TY T则f gh 0，（5分）n2其中 g 0,deg g,deg h.于是，若 h 0，则 fg 0，否则 f 1 h 0，所以n（5分）.AI ( f )2n因为 f是 F到 F 的映射，总有 f 1 f 0，于是22AI ( f ) deg f（5分）。