一类新的代数免疫度最优的奇变元旋转对称布尔函数的构造  

A New Construction of Odd-variable Rotation Symmetric Boolean Function with Optimal Algebraic Immunity

作　　者：王勇 郑东[1,2] 赵庆兰 李路阳[1] 师宇 WANG Yong;ZHENG Dong;ZHAO Qing-Lan;LI Lu-Yang;SHI Yu(National Engineering Laboratory for Wireless Security,Xi’an University of Posts and Telecommunications,Xi’an 710121,China;Westone Cryptologic Research Center,Beijing 100070,China)

机构地区：[1]西安邮电大学无线网络安全技术国家工程实验室,西安710121 [2]卫士通摩石实验室,北京100070

出　　处：《密码学报》2022年第4期644-662,共19页Journal of Cryptologic Research

基　　金：国家自然科学基金(61902314,62072371);陕西省自然科学基础研究计划(2019JQ867,2018JZ6001);陕西省教育厅专项科研计划(20JK0911);陕西省重点研发计划(2021ZDLGY06-02)。

摘　　要：布尔函数可以作为流密码和分组密码中的非线性部件,对密码系统的安全性有着重要的影响.旋转对称布尔函数是一类在输入进行循环移位下输出值保持不变的布尔函数.此类函数包含了很多具有良好密码学性质的布尔函数.如何构造具有最优代数免疫度的奇变元旋转对称布尔函数是布尔函数研究中的一个被广泛关注的问题.针对此问题沈黎鹏和陈克非给出了一种构造方案,所构造的函数非线性度在变元个数n> 23时是同类构造中最高的,但是在n≤23时是不确定的.本文给出一种新的构造方案,所构造的函数具有较高的非线性度,在变元个数n≤23时非线性度是同类构造中最高的,并且在某些情况下其代数次数能达到最高值n-1.此外,在变元个数为11, 13, 15时,利用Simon Fischer的程序验证了新构造的布尔函数具有几乎最优的抵抗快速代数攻击的能力.本文的构造可以为对称密码算法(尤其是利用小变元布尔函数作为非线性部件的轻量级密码算法)的设计提供更多可选择的密码函数.Boolean functions used as non-linear components in stream cipher and block cipher play an important role in the security of the cryptograph systems. Rotation symmetric Boolean functions are a class of Boolean functions which have unchanged output value under the cyclic shift of the inputs.This class of functions contains many Boolean functions with good cryptographic properties. How to construct odd-variable rotation symmetric Boolean functions with optimal algebraic immunity is a widely concerned problem. Shen and Chen proposed a construction for this problem. The nonlinearity of their constructed function is the highest in the similar construction when the number of variables n > 23, however, the nonlinearity is uncertain when n ≤ 23. In this paper, a new construction is given. The nonlinearity of the new functions is the highest among the similar constructions when the number of variables is less than 23, and in some cases its algebraic degree can achieve the highest value n-1. In addition, using Simon Fischer’s computer program it can be shown that the new functions have almost optimal resistance against fast algebraic attacks when the number of variables is 11, 13,or 15. The construction in this paper can provide more good choices for the design of cryptographic algorithms, especially for lightweight cryptographic algorithms which usually utilize Boolean functions with a small number of variables as non-linear components.

关 键 词：旋转对称布尔函数 代数免疫度 非线性度 代数次数 代数攻击 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]