旋转对称布尔函数研究综述  

A Survey on Results of Rotation Symmetric Boolean Functions

作　　者：高光普 

机构地区：[1]信息工程大学数学与先进计算国家重点实验室,郑州450001 [2]中国科学院信息工程研究所信息安全国家重点实验室,北京100093

出　　处：《密码学报》2017年第3期273-290,共18页Journal of Cryptologic Research

基　　金：国家自然科学基金(61402522)

摘　　要：布尔函数是许多密码系统的核心部件,其密码学性质的优劣决定着整个密码系统的安全性.因此研究和构造满足各种密码学性质的布尔函数是密码学研究领域的热点问题.旋转对称(Rotation Symmetric)函数也称幂等函数,是一类输出值在输入的循环移位下保持不变的布尔函数,具有结构简单、运算速度快、资源利用率高等优点,目前已被应用于分组密码S盒和压缩函数的设计中.本文综述了旋转对称函数的研究成果,具体包括:密码学性质优良的旋转对称布尔函数的搜索、旋转对称bent和semi-bent函数的构造、有限域上幂等函数的性质、代数免疫最优的旋转对称布尔函数的构造、线性结构特征、汉明重量和非线性度计算以及仿射等价性.其中重点归纳了近年来利用线性子空间构造旋转对称bent和semi-bent函数的构造方法,介绍了计算低次旋转对称布尔函数汉明重量以及非线性度的递归方法,提出了若干值得研究的公开问题.Boolean functions play an important role in cryptography since the resistance of cryptosystems is related to the complexity of the involved Boolean functions. Cryptanalysis and constructions of Boolean functions with certain cryptographic properties are two main problems in the field of cryptographic Boolean functions. Rotation symmetric Boolean functions, also called idempotent, which are invariant under circular permutations of the coordinates, have recently proven to be very useful in several areas of cryptography, especially for resource-constrained devices as they can reduce the memory needed for storing the functions. Precisely, they have been applied to design symmetric cryptosystems and Hash functions currently. In this paper, we survey the important results of rotation symmetric Boolean functions, including: cryptographically important rotation symmetric Boolean functions obtained by designing computer algorithms, constructions of rotation symmetric bent and semi-bent functions, constructions of rotation symmetric Boolean functions with algebraic immunity, correlation immunity etc. We also collect some results about the linear structure and affine equivalence of rotation symmetric Boolean functions. We especially summarize the method of linear subspaces by which the rotation symmetric bent or semi-bent functions are constructed, and also the thread in computing the Hamming weight and nonlinearity of rotation symmetric Boolean functions with low algebraic degree.Finally, several important open problems are introduced at the end of this paper.

关 键 词：布尔函数 旋转对称 BENT Semi-bent 幂等函数 平衡性 非线性度 相关免疫 代数免疫 线性结构 仿射等价 

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