布尔函数的密码性质及其相互关系

1、布尔函数的密码学性质及其相互关系摘要：本文的主要工作是对布尔函数的密码学性质进行简单的介绍以及整理，并将近期密码函数安全性领域里面的主要结论进行归纳和比较，通过各种性质及之间相互关系找出一种构造具有“优秀”密码学性质的函数的方法。本文第一部分为基本概念，主要内容是布尔函数的基本知识以及文章中将会用到的相关符号和语言。这一部分还简单介绍了布尔函数的两个基本性质：均衡性、代数次数。这两个性质对函数的安全性具有十分重要的意义。第二部分介绍了布尔函数的相关免疫性以及弹性的有关内容，末尾简单地介绍了几种构造具有特定相关免疫阶的布尔函数的方法。第三部分介绍了布尔函数的非线性度以及具有最高非线性度的Bent

2、函数的相关内容。这一部分最后还给出了两个完善Bent函数以使其均衡的方法。第四部分简单地介绍了布尔函数差分均匀度和PN函数的相关内容，并且给出了一个PN函数的等价定义。第五部分简单介绍了布尔函数的代数免疫度的概念。第六部分给出了许多重要的结论，这些结论揭示了各种密码函数性质之间的内在联系. 这一部分主要以总结归纳为主，适当加入笔者对结论的一些观点. 第一部分：基本概念定义1.1 设是二元有限域，为正整数，称映射为布尔函数. 若记全体维布尔函数的集合为. 使得且的的个数称为函数的Hamming重量，记为. 如果一个维布尔函数满足，则称这个函数是均衡的. 设,和的Hamming距离定义为其中，表示

3、集合中元素的个数. 容易发现:. 维布尔函数的代数正规型：为了方便书写，记表示的幂集，其中，则其中，.这种表示方法称为布尔函数的小项表示.在维布尔函数的代数正规型中，系数不为0的项的最高次数称为该函数的代数次数，记为. 特殊地， 代数次数为1的布尔函数称为仿射函数. 常数项为0的仿射函数称为线性函数. 含有高于1次的项的布尔函数称为非线性函数. 易证：仿射函数都是均衡的. 从布尔函数的代数正规型中可以发现：代数次数越低的布尔函数越容易被确定，这是因为我们可以将看成未知数，代数次数越低的函数未知数越少，那么我们就可以用越少的真值对将其确定出来. 因此，代数次数越低的布尔函数越不适合用作密码函数.

4、 在上面的介绍中，有两个性质对于一个布尔函数能否“胜任”密码函数来说有着十分重要的意义：均衡性、代数次数：均衡性：序列密码体制产生的密钥流是否具有高的安全强度，取决于它们是否具有良好的伪随机性. 均衡性就是序列伪随机性的一个重要指标. 一条序列称为均衡的是指该序列中不同元素出现的次数至多只相差一个. 代数次数：密码体制中所使用的布尔函数通常具有高的代数次数，低代数次数的密码体制容易遭到Berlekamp-Massey算法攻击、插值攻击、代数攻击以及高阶差分攻击. 以上为第一部分的主要内容，即布尔函数的基本内容. 从第二部分开始，我们将对布尔函数的多种密码性质进行整理、归纳和总结，并将近期密码学

5、界的相关结论呈现出来. 第二部分：布尔函数的相关免疫性 这一部分主要介绍了布尔函数相关免疫性的内容，包括相关免疫的定义以及它的一些等价刻画、布尔函数的Walsh变换与其相关免疫性的关系、如何构造具有特定阶的相关免疫函数及其记数. 下面先给出相关免疫性的定义：定义2.1 设有布尔函数. 如果维随机变量在上均匀分布；对下标集中任意个下标，随机变量与个随机变量相互独立,即对于任意的及就称为阶相关免疫布尔函数. 如果是阶相关免疫布尔函数但不是阶相关免疫函数，则称函数的相关免疫阶为. 下面的结论是维布尔函数相关免疫性的等价刻画：定理2.1 以下四个叙述等价：维布尔函数是阶相关免疫函数. 对任意的，令的任

6、意个分量取任意定值，维布尔函数是阶相关免疫函数. 对任意的，随机变量与变量相互独立. 对任意的，, 函数是平衡函数. 以上对于相关免疫性的描述对于理解布这个性质的本质还具有一定的困难. 布尔函数的Walsh变换对于理解其本质有着至关重要的作用：定义2.2 设是一个维布尔函数. 取，令. 称为的循环Walsh变换. 其中，定理2.2 设维布尔函数. 若，则是阶相关免疫函数的充要条件是对于所有且，. 上面的定理刻画了阶相关免疫函数的谱特征，对理解相关免疫性的实质有着非常大的帮助. 下面介绍具有均衡性的相关免疫函数弹性函数：定义2.3 设维布尔函数，若函数既是一个阶相关免疫函数又是均衡函数，则称是一

7、个阶弹性函数. 注意到布尔函数是均衡的当且仅当，于是定理2.3 布尔函数是一个阶弹性函数的充要条件是对于所有的且，均有. 在密码学研究中，密码函数的均衡性是密码函数的最基本的性质，所以一下讨论都将围绕弹性函数展开. 下面将简单地介绍一下弹性函数的构造. 由于一阶弹性函数的构造方法比较复杂，而且方法种类繁多，这里将省略介绍之. 参考文献1中有比较详细的关于一阶弹性函数的构造方法. 这里介绍一下如何通过已知的弹性函数构造新的弹性函数. 定理2.4 设是维阶弹性函数，则是维阶弹性函数. 定理2.5 设是维阶弹性函数，是维阶弹性函数，则是维阶弹性函数. 定理2.6 若函数均是维阶弹性函数，则函数也是阶

8、弹性函数的充要条件是是阶弹性函数. 这一部分最后将给出几个关于循环Wlash变换的结论，循环Wlash变换的定义已经由定义2.2给出. 定义2.4设是一个维布尔函数. 称为的线性Walsh变换. 其中，的定义如上. 称为的线性Walsh反变换，容易验证，线性Walsh变换与循环Wlash变换之间存在着如下关系：由此可知两种Walsh变换可以相互唯一确定，所以以后不加说明的话布尔函数的Walsh变换指的就是循环Walsh变换. 容易验证布尔函数的循环Walsh变换有如下性质：定理2.7 若为的循环Walsh变换，即，那么，称为的循环Walsh逆变换，且. 能量守恒公式：. 卷积公式：对于任意的，

9、 . 第三部分：布尔函数的非线性度 布尔函数的非线性度从形象上说指的是布尔函数与仿射函数之间的“距离”. 为了抵抗线性密码攻击，密码体制中所使用的布尔函数应该离所有的仿射函数的“距离”尽可能大. 所以布尔函数的非线性度定义为和所有仿射函数的最小Hamming距离. 定义 3.1 设是一个维布尔函数，称如下的为的非线性度，其中表示所有维仿射函数的集合. 定理3.1 设是一个维布尔函数，则其中，是的循环Walsh变换. 这个定理给出了布尔函数非线性度的计算方法，下面的定理给出一个布尔函数的非线性度紧的上界. 定理3.2 设是一个维布尔函数，则它的非线性度满足定理3.2中的上界是可达的. 定义3.2

10、设是一个维布尔函数，如果的非线性度达到，那么称为Bent函数 定理3.3 设是一个维布尔函数，则是Bent函数当且仅当对任意的，的取值只能是. 容易发现，Bent函数的维数必定为偶数. 定义3.2和定理3.3都可以作为Bent的定义，其本质是相同的. Bent函数是非线性度最高的布尔函数，下面给出一些关于Bent函数的结论. 定理3.4 （存在性）设为任意正偶数，令则是一个元Bent函数. 定理3.5 设是维Bent函数，是上的阶可逆方阵，令，则也是维Bent函数. 定理3.6 设是任意一个维布尔函数数，则是维Bent函数. 虽然Bent函数拥有最高的非线性度，但是Bent函数却没有作为密码函

11、数最基本的性质均衡性. 下面简单地给出两个构造方式，可以通过对Bent函数进行改造，使其具有均衡性. 定理3.7 高非线性度均衡布尔函数构造方法构造方法1. 取定个维Bent函数，其中. 其中的个函数满足另外个函数形状为定义维布尔函数，则且均衡. 构造方法2. 设有维Bent函数，定义维布尔函数如下：则，且均衡. 第四部分：布尔函数的差分均匀度以及完全非线性函数 差分分布的均匀性是密码函数的一个重要的安全性指标，差分密码分析方法的成功正是通过布尔函数差分分布的不均匀性实现的. 函数的差分均匀性越好，那么函数抵抗差分攻击的能力就越强. 用来刻画布尔函数查分分布均匀性的指标是差分均匀度. 定义4.

12、1 设是从有限群到有限群的函数，令则称为函数的差分均匀度. 定理4.1 设是从有限群到有限群的函数，则 由之前的谈论知差分均匀度越小，布尔函数的安全性就越高. 定理4.1给出了差分均匀度的一个下界，由此引出完全非线性函数的概念： 定义4.2 设是从有限群到有限群的函数，且，如果，则称为完全非线性函数，简称PN函数. 为了给出一个完全非线性函数的等价定义，首先引入一个概念平衡函数： 定义4.3 设是从有限群到有限群的函数，称为平衡函数是指，对于任意的，集合中所含的元素个数相等. 也即如群的阶是，群的阶是，则. 下面给出PN函数的等价刻画： 定理4.2 设是从有限群到有限群的函数，且.那么是PN函

13、数当且仅当对任意的非零，函数为平衡函数. 这个定理反映了PN函数的本质特征，即它的差分分布的均匀性已经达到最优，对于差分均匀度和完全非线性函数的介绍也就到此为止. 第五部分：布尔函数的代数免疫度 布尔函数的代数免疫度是对一个布尔函数抵抗代数攻击能力的衡量标准，也是密码函数安全性的一个重要指标. 代数免疫度低的布尔函数容易遭到代数攻击，代数攻击所利用的理论依据与差分攻击和线性攻击等攻击手段不一样. 前者是利用密码算法的内部代数结构实施攻击，而后者则是利用密码算法的统计性质实施攻击. 然而，对布尔函数实施代数攻击能否成功的关键在于是否存在一个低次的函数，使得. 定义5.1 设维布尔函数，称满足的布

14、尔函数为布尔函数的零化子. 对任意的维布尔函数，记其零化子的集合为 定义5.2 设维布尔函数，使得或成立的非零布尔函数的最小代数次数称为的代数免疫度，记为. 即 下面的定理给出了代数免疫度的上界. 定理5.1设是维布尔函数，则的代数免疫度满足： 定义5.3 若一个维布尔函数的代数免疫度达到，则称该函数具有最优代数免疫度. 有关代数免疫度的结论，更多的是与其他密码性质放在一起讨论的. 如具有固定代数免疫度是函数的非线性度具有一个紧的下界，代数免疫度确定是函数的相关免疫阶和弹性阶的取值规律，代数免疫度与函数的重量也有密切的关系. 如此多的性质和结论将在第六部分给出. 第六部分：布尔函数密码性质之间

15、的相互关系 构造一个具有好的密码学性质的密码函数是密码学研究者们梦寐以求的事情，然而大量的结果表明这些密码学性质之间存在着相互制约的关系.一种性质好了另一种性质就会受到制约而变差. 正是因为如此，构造一个性质“兼顾”的布尔函数也成了比较困难的事. 这一部分将给出各性质之间相互的关系，以便从中找到一种构造“优质”密码函数的方法. 密码函数的安全性指标在第一、二、三、四、五部分中均已介绍，指的是布尔函数的均衡性、代数次数、相关免疫性和弹性、非线性度、差分均匀度以及代数免疫度. 1. 相关免疫性与其他性质的关系 定理6.1 设维布尔函数，若是阶相关免疫函数，则；若是阶弹性函数，则. 这个定理说明了布

16、尔函数的相关免疫性和弹性与函数的代数次数相互制约. 定理6.2 给定维布尔函数，若是阶相关免疫函数，则若是阶弹性函数，则 这个定理揭示了布尔函数相关免疫性和弹性与非线性度的相互制约关系. 定理中的非线性度的上限被称作Sarkar限. 2. 非线性度与其他性质的关系 由第三部分我们知道Bent函数具有最高的非线性度，下面的定理说明了Bent函数的一些其他密码学性质. 定义6.1 设是一个维布尔函数，其自相关函数定义为自相关函数刻画了布尔函数的自相关性，这个概念可以与序列的自相关性类比理解. 定理6.3 设是一个维布尔函数，则是Bent函数当且仅当这个定理表明Bent函数是具有最有自相关性的布尔函

17、数. 定理6.4 设是一个维布尔函数，若是Bent函数，则它的代数次数不超过. 这个定理表明了函数的非线性度与函数的代数次数之间存在着相互制约的关系. 定理6.5 设维布尔函数，其非线性度与其相关免疫阶有如下的关系： 有这个定理知道布尔函数的非线性度与相关免疫阶呈负相关. 3. 代数免疫度与其他性质的关系第五部分定理5.1给出了布尔函数的代数免疫度与代数次数的关系：设是维布尔函数，则的代数免疫度满足： 定理6.6 设维布尔函数，的代数免疫度，则特别地，意味着（1）当为奇数时，必为平衡函数；（2）当为奇数时， 这个定理没有揭示代数免疫度与其他性质的关系，它是联系代数免疫度和函数Hamming重量

18、的重要事实. 定理6.7 设维布尔函数，则 定理6.8 对于任意的正整数和，定理6.7中的界是紧的. 这两个定理告诉我们函数的代数免疫度和函数的非线性度存在着相互制约的关系，但是这种制约关系是可以被估计的，并且这个界可以达到. 定理6.9 设为维阶相关免疫函数，则；若还是均衡的，即是阶弹性函数，则 这个定理是定理6.1的直接推论. 联合定理6.5，可以马上得到一个新的结果： 定理6.10 设为维布尔函数，若是阶相关免疫函数，则若是阶弹性函数，则 这两个定理都说明了布尔函数的代数免疫度与相关免疫性之间的关系，可以发现这两者之间也存在着负相关性. 可以发现布尔函数的各项密码学性质均存在着相互的制约关系，如何构造一个性质中庸、抗攻击性强的布尔函数依然是现今比较流行的话题. 参考文献1 李超,屈龙江，周悦. 密码函数的安全性指标分析 M. 第一版. 科学出版社，2011. 2 冯国登. 频谱理论及其在密码学中的应用 M. 科学出版社，2000. 3 Carlet C. On bent and highly nonlinear balanced/resilient functions and their algebraic immunitiesC. AAECC 16,LNCS 3857. Springe