布尔函数的(快速)代数免疫性质研究进展

摘要

布尔函数是流密码算法中伪随机密钥流序列生成器的核心部件之一.为了抵抗已知的密码攻击手段,基于线性反馈移位寄存器的流密码算法中所使用的非线性布尔函数必须兼具可证明的能够抵抗已知密码攻击的性能.在2003年之前,为了避免密码系统遭受基于统计分析的概率攻击,布尔函数应满足平衡性;为了抵抗最佳仿射逼近和快速相关攻击,布尔函数应具有高的非线性度;为了抵抗Berlekamp-Massey算法攻击和R?njom-Helleseth攻击,布尔函数应具高的代数次数;为了减少布尔函数的输出比特与输入变量分量之间的统计相关性,为密码系统提供扩散特性,布尔函数应具有良好的自相关性质;为了抵抗分别征服攻击和相关攻击,应用于组合模式中的布尔函数还应当满足高阶弹性.2003年,Courtois和Meier在欧洲密码学年会上将代数攻击应用于基于线性反馈移位寄存器的流密码算法,同年,Courtois在国际密码学年会上提出快速代数攻击方法.为了抵抗代数和快速代数攻击,布尔函数应分别具有高的代数免疫度和良好的快速代数免疫度.本文总结了近十余年来国内外学者在构造最优代数免疫布尔函数相关方面的主要研究进展.