代数免疫函数的性质与构造

Before 21st century, cryptographic Boolean functions were required to satisfy cryptographic criteria such as balancedness, a high algebraic degree, a high nonlinearity, a high correlation immunity and so on, for resisting many known cryptographic attacks. Since 21st century, algebraic attacks have been regarded as the most successful attacks on stream ciphers based on linear feedback shift registers. Thus the algebraic immunity was introduced to measure the ability of Boolean functions to resist standard algebraic attacks, and has been considered as one of cryptographically significant properties for Boolean functions. After this, the properties and constructions of Boolean functions with maximum algebraic immunity have been researched in a large number of papers. However, a high algebraic immunity is not sufficient for resisting fast algebraic attacks. The theory of the resistance of Boolean functions against fast algebraic attacks still need to be perfect. This research mainly focuses on the immunity of Boolean functions against algebraic attacks and constructions of algebraic immune functions. First, to develop the theory of resistance to fast algebraic attacks, we will study the properties and constructions of perfect or almost perfect algebraic immune functions. Then, to further perfect the theory of resistance to algebraic attacks, we will research the constructions of algebraic immune functions with other good cryptographic properties. Finally, to provide fundamental basis for designing ciphers, we will investigate the constructions of Boolean functions with all main cryptographic properties.

21世纪以前，为抵抗许多已知的密码攻击，要求密码学中的布尔函数满足平衡性、高代数次数、高非线性度、高相关免疫度等密码学准则。21世纪以来，代数攻击被认为是对线性反馈流密码最成功的攻击，因而代数免疫度被提出用以衡量布尔函数抵抗标准代数攻击的能力，成为布尔函数的重要密码学性质之一。此后，涌现了大量关于最优代数免疫度布尔函数性质及构造的研究成果。然而，高代数免疫度并不足以抵抗快速代数攻击。在布尔函数抵抗快速代数攻击的免疫性方面，现有理论尚不完善。本课题主要研究布尔函数的代数免疫性和代数免疫函数的构造问题。首先，研究完全代数免疫函数或几乎完全代数免疫函数的性质及构造，发展快速代数免疫性理论；其次，研究具有多种密码学性质的代数免疫函数构造，进一步完善代数免疫性理论；最后，研究满足所有主要密码学准则的布尔函数构造，为设计密码体制提供理论基础。

布尔函数在密码学中有非常重要的地位，流密码中的密钥流生成函数和分组密码中的 S 盒都由布尔函数组成，hash 函数的设计也与布尔函数密切相关。项目组主要针对代数免疫函数的性质与构造及其相关课题进行了深入研究，并取得了一系列的研究成果。1）刻画了循环对称布尔函数的代数免疫性和非线性度，提出了有效计算循环对称布尔函数的快速代数免疫性的算法，并首次构造了一类变元个数为2的幂次的三次循环对称bent函数。2）成功证明了公开文献中一类已知的布尔函数是几乎完全代数免疫函数，并在此基础上，构造了一类具有多种密码学性质的几乎完全代数免疫函数，发展和完善了布尔函数的代数免疫性理论。3）研究了布尔函数的代数性质，并成功地应用于序列密码算法Trivium和杂凑函数SHA-3等经典对称密码算法的安全性分析中，得到了目前为止Trivium最好的区分攻击和SHA-3最好的碰撞攻击。