布尔函数代数免疫度的研究

  姓   名：解永宏     学科专业：信息安全

   研究方向：密码学    指导教师：胡磊 教授

 摘    要

 布尔函数是对称密码体制的一个基本组成部分，一个安全的密码系统要求它所使用的布尔函数必须具备良好的密码学性质，这些性质主要包括：平衡性、代数次数、非线性度、相关免疫度和代数免疫度等。因此，研究布尔函数的密码学性质是十分有意义的。

 代数攻击是一种新兴的密码分析算法，对某些流密码和多变量密码，它是一种十分有效的分析方法。代数免疫度刻画了布尔函数抵御代数攻击的性能。本文主要研究了布尔函数代数免疫度这一密码学性质，主要内容包括：布尔函数零化集性质的研究、最优代数免疫度函数的构造，以及研究了一类布尔函数的密码学性质。

 1.我们借助线性映射和矩阵的语言描述了布尔函数零化子集合的结构，在此基础上，对奇数元平衡布尔函数及其补函数，探讨了它们零化子集合之间关系。具体而言，我们用n元布尔函数的系数向量来表示这个函数f，对任意n元函数g，乘积fg可以看做是在$\F_{2}^{2^n}$上对g对应的向量做一个固定的线性变换。利用f的零化子所组成的集合是这个线性变换核空间这一点，我们研究了布尔函数零化子集合的一些代数性质。互补函数的零化子集合之间的一般关系，是代数免疫度研究中的一个公开问题。我们对奇数元平衡布尔函数及其补函数的零化集的维数性质进行了研究，并得到一个维数等式。

 2.研究了目前构造具有极大代数免疫度布尔函数的方法，给出了一种利用可逆矩阵来构造极大代数免疫度函数的方法及其计数。根据f代数标准型的性质，可以得到一个关于其零化子$g$的系数的方程组，我们通过构造具有特殊形状的系数矩阵使得f达到代数免疫度最优。所构造的函数是平衡的，代数次数达到了平衡函数所能达到的最高次数，并对构造函数做了计数。

 3.我们构造了一类具有4个Walsh谱值的布尔函数，它的迹表示为$f(x)=\tr_1^n\left(x^{d(2^{n}+1)}\right)+\tr_1^{2n}(bx)$。我们研究了它的密码学性质，这类函数是平衡的且具有次优的非线性度和较高的代数次数，另外，数值计算的结果显示此类函数的代数免疫度能够达到最优或次优。