布尔函数快速代数免疫度关键问题研究

For allowing resistance to the fast algebraic attacks, Boolean functions used in cryptosystems must have high fast algebraic immunity. Up to now, there are only a few known results on the fast algebraic immunity of Boolean functions and there are many problems to the fast algebraic immunity of Boolean functions needed to be solved. The research objective of this project is to obtain several new results on the fast algebraic immunity of Boolean functions. Based on the product properties of two Boolean functions and the well-known Lucas’ theorem, we first get some new relations between the fast algebraic immunity and others cryptographic properties of Boolean functions. Second, by studying the properties of the vector space formed by the annihilators of Boolean functions and the product properties of two Boolean functions, we deduce new relations between the fast algebraic immunity of a Boolean function and that the fast algebraic immunity of its revised function. Finally, by means of the univariate and bivariate polynomial representations of Boolean functions defined on finite fields, we propose some constructions of balanced and 1-resilient Boolean functions with optimal algebraic immunity, having provable high fast algebraic immunity and high nonlinearity.

为了抵抗快速代数攻击，应用于流密码系统中的布尔函数应具有高的快速代数免疫度。目前关于布尔函数快速代数免疫度的相关研究结果较少，许多关键问题亟待解决。本项目拟对布尔函数快速代数免疫度的关键问题展开深入研究：1. 通过研究布尔函数间的乘积性质以及组合中的Lucas定理，进一步刻画出布尔函数快速代数免疫度与其他密码学性质之间的关系；2. 以研究布尔函数零化子构成的线性空间的结构以及布尔函数间乘积的性质为突破点，理论推导出布尔函数与其修改函数的快速代数免疫度之间的关系；3. 基于布尔函数在有限域上的一元和二元多项式表示，构造具有可证明高快速代数免疫度和高非线性度下界的最优代数免疫平衡布尔函数和1阶弹性布尔函数。

布尔函数作为对称密码算法核心模块的重要组成部分，其密码性能决定密码算法的理论安全界。为了抵抗快速代数攻击，应用于流密码系统中的布尔函数应具有高的快速代数免疫度。目前关于布尔函数快速代数免疫度的相关研究结果较少，许多关键问题亟待解决。本项目对布尔函数快速代数免疫度的若干关键问题展开了深入研究，主要完成以下工作：（1）基于布尔函数在有限域上的二元多项式表示，构造了一簇具有最优代数免疫度和最优代数次数的1阶弹性布尔函数，并从数学理论上首次严格证明了该类函数具有高的快速代数免疫度；（2）完全刻画出布尔函数的快速代数免疫度与其修改函数的快速代数免疫度二者之间的关系，由此率先确定了几类通过修改择多逻辑函数得到的布尔函数的快速代数免疫度上界；（3）研究了与布尔函数快速代数免疫度密切相关的两个密码学性质：自相关性质和高阶非线性。在自相关性质研究方面，首次构造出Zhang-Zheng猜想的一个无限类反例；在高阶非线性度研究方面，给出或提高了几类特殊布尔函数的高阶非线性度下界。围绕以上研究成果，项目负责人唐灯以第一/通讯作者身份在国内外重要学术期刊和学术会议上发表标注基金资助的高水平研究论文22篇，其中SCI源期刊论文18篇、国际会议EI检索论文3篇，含以第一作者在密码与信息理论旗舰期刊《IEEE Transactions on Information Theory》上发表期刊论文2篇，以通讯作者在密码与编码领域著名期刊《Designs, Codes and Cryptography》上发表期刊论文1篇，以第一作者在密码与组合设计著名期刊《SIAM Journal on Discrete Mathematics》和《Discrete Mathematics》上发表期刊论文各一篇。项目负责人唐灯获评2019年密码算法学术会议最佳论文，参与提交至中国密码学会主办的“全国密码算法设计竞赛”的分组密码算法FBC获评三等奖，破格晋升副教授、获评博士生导师。项目培养/协助培养硕士研究生四名，3人获评研究生国家奖学金。