布尔函数代数免疫性研究

代数攻击是近几年发展起来的一种新的密码分析方法，对许多密码系统都构成很大的威胁。随着代数攻击的出现，也提出了关于布尔函数安全性的一个新准则- - 代数免疫度，它衡量了布尔函数抵抗标准代数攻击的能力。为了有效抵御代数攻击所带来的冲击，密码系统必须使用代数免疫度较高（甚至代数免疫最优）的布尔函数。本项目研究布尔函数的代数免疫性：首先，研究所有对称布尔函数和某类轮换对称布尔函数达到代数免疫最优的充要条件，并分析这些函数的其它密码学性质，以期找到在各种密码学性质上均表现优良的布尔函数，来满足现实需求；同时，从新的角度入手，探索构造代数免疫最优布尔函数的新型方法；此外，还将引入交换代数中的Gr?bner基计算工具，提出具有更高计算效率的新算法，来计算布尔函数的代数免疫度和零化子。在代数攻击的背景下，研究布尔函数的代数免疫性，特别是代数免疫最优布尔函数的构造，不但有着特殊的理论意义，更具有重要的现实意义。

代数攻击的出现对许多密码系统都构成威胁。为了有效抵御代数攻击所带来的冲击，密码系统必须使用代数免疫度较高的布尔函数。本项目主要研究布尔函数的代数免疫性，包括以下内容：. 首先，关于代数免疫最优的轮换对称布尔函数。在择多函数的基础上，通过改变某些特殊轨道的函数值，得到偶数变元代数免疫最优的轮换对称布尔函数。在此基础上加入满足一定性质的轨道簇，可得到数量更多的布尔函数；对于奇数变元的情形，则在基于整数拆分理论来选取可改变函数值的轨道簇，从而得到既满足代数免疫最优又具有较高非线性度的布尔函数。而且，从不同的选取角度出发，将得到数量更加丰富的函数。. 其次，关于代数免疫最优的对称布尔函数。研究了代数免疫最优对称布尔函数的标准型：均可表示为择多函数与两类特定函数中的若干个之和。同时也研究了该类函数的代数次数和非线性度，借助标准型的表达方式，给出了非线性度的准确计算式。. 再次，关于代数免疫最优的布尔函数。主要研究了代数免疫最优布尔函数的递推构造。首先针对奇数变元的特点，将之前的二阶递归构造法加以改进，得到平衡的布尔函数。同时引入函数变换，得到一系列的构造方法。最后将上述构造法从二阶递归推广到一阶递归，得到更加丰富的递归构造法。. 最后，关于代数免疫性的快速计算。函数f 的代数免疫度就是理想<f+1>和理想<f>中多项式的最低代数次数。利用Grobner基的快速算法，结合二元域GF(2)的特殊性，设计计算理想中多项式次数的快速算法。但由于Grobner基算法的复杂性，在具体计算上，对于GF(2)上的不同多项式，表现出不同的效率。目前尚未分析出明确的科学规律。