任意偶变元上代数免疫度最优的平衡旋转对称布尔函数的构造  

Construction of Balanced Rotation Symmetric Boolean Functions with Optimal Algebraic Immunity on Arbitrary Even Variables

作　　者：赵庆兰[1] 李盼 郑东[1] 李梦苒 张建东 ZHAO Qing-Lan;LI Pan;ZHENG Dong;LI Meng-Ran;ZHANG Jian-Dong(National Engineering Research Center for Secured Wireless,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

机构地区：[1]西安邮电大学无线网络安全技术国家工程研究中心,西安710121

出　　处：《密码学报（中英文）》2024年第4期924-944,共21页Journal of Cryptologic Research

基　　金：国家自然科学基金(61902314)。

摘　　要：旋转对称布尔函数是一类在输入进行循环移位的条件下输出保持不变的布尔函数.此类函数因具有特殊的结构并且包括许多具有良好密码学性质的布尔函数而在密码学领域受到广泛关注.在代数攻击出现之后,如何构造出具有最优代数免疫度的平衡旋转对称布尔函数成为布尔函数相关研究中的一个热点问题.对于这个问题的研究,在任意奇数变元上已经有了丰富的成果,而在任意偶变元上构造此类函数一直以来都是一件具有挑战性的工作.2021年,Mesnager等人提出了一类构造方法成功解决了这个难题,但所构造函数的非线性度不高.本文在任意偶变元n上给出了一类新的旋转对称布尔函数构造方法,所构造的函数不仅具有最优代数免疫度和平衡性,同时其非线性度在变元个数n大于等于8时均高于现有的任意偶变元上的同类构造.除此之外,通过电脑程序得到了这类新函数在变元个数小于等于16时不仅具有良好的抵抗快速代数攻击的能力而且代数次数可达到最高值n−1或次高值n−2.Rotation symmetric Boolean functions are a class of Boolean functions whose output remains unchanged under the cyclic shift of the input.These functions have received much attention in cryptography because of their special structure and the fact that they include many functions with good cryptographic properties.After the emergence of algebraic attacks,the construction of balanced rotation symmetric Boolean functions with optimal algebraic immunity has become a hot topic in the study of Boolean functions.The study of this topic has been rich in arbitrary odd variables,but has been a challenging work on those in arbitrary even variables.In 2021,Mesnager et al.proposed a construction method that successfully solved this problem,however the nonlinearity of their constructed functions is not high.This paper presents a new construction method of rotation symmetric Boolean functions on arbitrary even variables n,which can ensure that the constructed functions have optimal algebraic immunity and good balancedness,as well as higher nonlinearity than the existing constructions for arbitrary even variables when n is greater than or equal to 8.In addition,when n is not greater than 16,experiments show that those functions have good resistance against fast algebraic attacks,and the algebraic degree can reach the highest values n−1 or the almost highest values n−2.

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

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