文档介绍：-1-
布尔函数的密码学性质及其相互关系
摘要：本文的主要工作是对布尔函数的密码学性质进行简单的介绍以及整理，并将近期密码函数安全性领域里面的主要结论进行归纳和比较，通过各种性质及之间相互关系找出一种构造具有“优秀”密码学性质的函数以下四个叙述等价：
n维布尔函数f是邙介相关免疫函数.
对任意的S<t,令(x,xx)的任意s个分量取任意定值，n-s维布尔函数
12n
f是t-s阶相关免疫函数.
对任意的C二(c,c，…,c),W(c)<t，随机变量y二(x,xx)与变量
12nH12n
c-x二cx+cx+...+cx相互独立.
1122nx
［2］对任意的c=(c,c，…,c),W(c)<t,函数y+c-x是平衡函数.
尔函数的Walsh变换对于理解其本质有着至关重要的作用：
(x)=(w,w,w)eF，令
12n2
w-x二wx+wx+...+(w)为f(x)，
1122nxf
S(w)(-1)f(x)+wx
f
x
<t<n，则f是t阶相关免疫函数的充要条
件是对于所有weFn且1<W(w)<t，S(w)=0.
Hf
上面的定理刻画了t阶相关免疫函数的谱特征，——弹性函数：
⑴设n维布尔函数f，若函数f既是一个t阶相关免疫函数又是均衡
函数，则称f是一个t阶弹性函数.
注意到布尔函数f是均衡的当且仅当Sf(0)=0，于是
［1］布尔函数f是一个t阶弹性函数的充要条件是对于所有的we乌
且0<W(w)<t，均有S(w)二0.
Hf
在密码学研究中，密码函数的均衡性是密码函数的最基本的性质，所以一下讨论都将围绕弹性函数展开.
-4-
，而且方法种类繁多，[1].
，则
h(x,x，…，x,x)二f(x,x，…，x)+x(f(x,x，…，x)+f(1+x,1+x,...,1+x))
12nn+112nn+112n12n
是n+1维t+1阶弹性函数.
，g是m维s阶弹性函数，则
h(x，x，…，x
12n
，x)
n+m
，x)=f(x，x，x)+g(x，x
n+m12nn+1n+2
是n+m维t+s+1阶弹性函数.
[3]若函数f1(x)，f2(x)，f3(x)均是n维t阶弹性函数，则函数
g(x)二f1(x)+f2(x)+f3(x)也是邙介弹性函数的充要条件是
h(x)二f(x)f(x)+f(x)f(x)+f(x)f(x)
121323
是t阶弹性函数.
这一部分最后将给出几个关于循环Wlash变换的结论，.
(x)(w)为f(x)的线性Walsh变换.
其中，
F(w)f(x)(-1)w-x
x
w-(x)为F(w)的线性Walsh反变换，容易验证，
f(x)=丄工S(w)(-1)w-x
2nf
w
线性Walsh变换与循环Wlash变换之间存在着如下关系：
—2F(w)，w丰0
S(w)
f2n—2F(w)，w二0
由此可知两种Walsh变换可以相互唯一确定，所以以后不加说明的话布尔函数的
Walsh变换指的就是循环Walsh变换.
容易验证布尔函数f(x)的循环Walsh变换有如下性质：
-11-
-5-
(w)为f(x)的循环Walsh变换，即S屮(w)二工(—l)f(x)+wx，那么,
x
①/(x)称为Sf(w)的循环Walsh逆变换，且/(x)=
工S(w)(-1)
w-x
能量守恒公式：工(S(W))2=22".
f
卷积公式：对于任意的a丰0，工S(w)S(w+a)=0.
ff
w
第三部分：布尔函数的非线性度布尔函数的非线性度从形象上说指的是布尔函数与仿射函数之间的“距离”.为了抵抗线性密码攻击，密码体制中所使用的布尔函数应该离所有的仿射函数的“距离”
Hamming距离.
(x)是一个n维布尔函数，称如下的Nf