论文标题
探索由细胞自动机引起的半弯曲布尔功能
Exploring Semi-bent Boolean Functions Arising from Cellular Automata
论文作者
论文摘要
从密码学的角度来看，半弯曲的布尔函数很有趣，因为它们具有多种理想的特性，例如具有低和平坦的WALSH频谱，这对于抵抗线性隐性分析很有用。在本文中，我们考虑通过基于细胞自动机（CA）的结构来搜索半弯曲功能。特别是，该结构通过计算CA中所有输出单元的XOR来定义布尔函数。由于所得的布尔函数具有CA局部规则的代数程度相同，因此我们设计了一种组合算法来枚举所有二次布尔函数。然后，我们应用该算法来详尽探索最多6个变量的二次规则的空间，仅选择基于CA的构造始终产生的半弯曲功能的二次变量。最后，我们过滤了获得的平衡性规则，并指出通过我们的构造产生的半弯曲函数通过其余规则具有恒定数量的线性结构。
Semi-bent Boolean functions are interesting from a cryptographic standpoint, since they possess several desirable properties such as having a low and flat Walsh spectrum, which is useful to resist linear cryptanalysis. In this paper, we consider the search of semi-bent functions through a construction based on cellular automata (CA). In particular, the construction defines a Boolean function by computing the XOR of all output cells in the CA. Since the resulting Boolean functions have the same algebraic degree of the CA local rule, we devise a combinatorial algorithm to enumerate all quadratic Boolean functions. We then apply this algorithm to exhaustively explore the space of quadratic rules of up to 6 variables, selecting only those for which our CA-based construction always yields semi-bent functions of up to 20 variables. Finally, we filter the obtained rules with respect to their balancedness, and remark that the semi-bent functions generated through our construction by the remaining rules have a constant number of linear structures.
