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

Recent Progress in(Fast) Algebraic Immunity of Boolean Functions

作　　者：唐灯[1] 

机构地区：[1]西南交通大学数学学院,成都611756

出　　处：《密码学报》2017年第3期262-272,共11页Journal of Cryptologic Research

基　　金：国家自然科学基金青年科学基金项目(61602394);中央高校基本科研业务费专项资金资助(2682016CX113)

摘　　要：布尔函数是流密码算法中伪随机密钥流序列生成器的核心部件之一.为了抵抗已知的密码攻击手段,基于线性反馈移位寄存器的流密码算法中所使用的非线性布尔函数必须兼具可证明的能够抵抗已知密码攻击的性能.在2003年之前,为了避免密码系统遭受基于统计分析的概率攻击,布尔函数应满足平衡性;为了抵抗最佳仿射逼近和快速相关攻击,布尔函数应具有高的非线性度;为了抵抗Berlekamp-Massey算法攻击和R?njom-Helleseth攻击,布尔函数应具高的代数次数;为了减少布尔函数的输出比特与输入变量分量之间的统计相关性,为密码系统提供扩散特性,布尔函数应具有良好的自相关性质;为了抵抗分别征服攻击和相关攻击,应用于组合模式中的布尔函数还应当满足高阶弹性.2003年,Courtois和Meier在欧洲密码学年会上将代数攻击应用于基于线性反馈移位寄存器的流密码算法,同年,Courtois在国际密码学年会上提出快速代数攻击方法.为了抵抗代数和快速代数攻击,布尔函数应分别具有高的代数免疫度和良好的快速代数免疫度.本文总结了近十余年来国内外学者在构造最优代数免疫布尔函数相关方面的主要研究进展.Boolean functions are the building blocks of symmetric cryptographic systems. In order to have resistance against the known attacks on each model of stream cipher, Boolean functions should meet various criteria. Before 2003, the following criteria for Boolean functions used in stream ciphers with linear feedback are mandatory: balancedness(to avoid statistical dependence between the plaintext and the ciphertext), high nonlinearity(to withstand the best affine approximation and fast correlation attack), high algebraic degree(to withstand the Berlekamp-Massey and the R?njomHelleseth attacks), good autocorrelation properties(to provide the property of diffusion to the cryptosystems), and high order resiliency(to resist the Siegenthaler correlation attack in the case of the combiner model). At Eurocrypt 2003, Courtois and Meier successfully proposed an algebraic attack on several stream ciphers which were previously believed to be secure. The attack was further improved by Courtois at Crypto 2003 where the technique of fast algebraic attack was introduced. To resist the algebraic and fast algebraic attacks, Boolean functions used in stream ciphers with linear feedback should have(almost) optimal algebraic immunity and high fast algebraic immunity. In this paper,we present a survey on the recent progress in the constructions of Boolean functions with optimal algebraic immunity and high fast algebraic immunity.

关 键 词：布尔函数 非线性度 代数免疫度 快速代数免疫度 

分 类 号：TN918.1[电子电信—通信与信息系统]