抵御代数和快速代数攻击的布尔函数的性质与构造

Boolean functions are one of key elements in stream cipher designs. Boolean functions used in stream cipher should satisfy different kinds of cryptographic properties in order to help resist different types of cryptanalytic attacks. In this project several cryptographic properties of Boolean functions, including algebraic immunity, nonlinearity, correlation immunity, especially the resistance of Boolean functions against fast algebraic attacks, are investigated. There are three aspects in this project: the construction of resilient Boolean functions with large algebraic immunity and high nonlinearity, properties and constructions of Boolean functions with good resistance against fast algebraic attacks, and cryptographic properties of Boolean functions constructed from computationally hard problems.

布尔函数是流密码体制的一个重要设计元素。使用在流密码中的布尔函数应该具有各种密码性质以有助于抵御各种不同的密码攻击。本项目研究布尔函数的代数免疫性、非线性度和相关免疫性等几种密码性质，并着重考虑布尔函数抵御快速代数攻击的性能。研究内容可以分成三个方面：具有较大代数免疫度和较高非线性度的弹性布尔函数的构造，抵御快速代数攻击性能良好的布尔函数的性质与构造，基于计算困难问题构造的布尔函数的密码性质。

布尔函数是流密码体制的一个重要设计元素。使用在流密码中的布尔函数应该具有各种密码性质以有助于抵御各种不同的密码攻击。本项目着重考虑布尔函数抵御快速代数攻击的性能。主要在抵御快速代数攻击性能良好的布尔函数的判定和构造方面进行了研究。取得的研究结果主要有以下四个方面。对于在设计流密码时，分析、判定和选择抵御快速代数攻击性能良好的布尔函数，它们具有理论指导意义。首先，重新刻画了布尔函数抵御快速代数攻击的性能与布尔函数的代数免疫性之间的关系，深化了对布尔函数抵御快速代数攻击性能的认识。其次，给出了布尔函数抵御快速代数攻击性能（几乎）最优的一个简化的充分条件。利用这一充分条件，在判断一个给定布尔函数的抵御快速代数攻击的性能时，有可能少计算若干个矩阵的秩，从而减少实际的计算量。再次，对于布尔幂函数，给出了将原来在有限域GF(2^n)上的判定矩阵约化到有限域GF(2)上矩阵的一个充分条件，即如果给定的布尔幂函数满足这一条件，那么其抵御快速代数攻击的性能仅与其幂次相关。利用这一充分条件，通过计算机实验发现了几类14元和15元抵御快速代数攻击性能亚几乎最优的布尔幂函数。最后，提出了轮换对称代数免疫（RS-代数免疫）的概念，即在判定抵御快速代数攻击性能时仅考虑使用轮换对称布尔函数进行快速代数攻击的情形。考察了代数变元数小于等于15次数大于等于n-3并且系数为1的所有布尔幂函数的RS-代数免疫性，发现它们的RS-代数免疫性与其抵御快速代数攻击的性能完全相同，从而构造抵御快速代数攻击性能良好的布尔幂函数就等价于构造RS-代数免疫性好的布尔幂函数。RS-代数免疫性的判定矩阵具有更好的代数结构，这使系统地构造抵御快速代数攻击性能良好的布尔函数成为可能。