Highly Nonlinear Boolean Functions With Optimal Algebraic Immunity and Good Behavior Against Fast Algebraic Attacks
Highly Nonlinear Boolean Functions With Optimal Algebraic Immunity and Good Behavior Against Fast Algebraic Attacks
复制标题
DOI：
10.1109/tit.2012.2217476
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
Deng Tang;C. Carlet;Xiaohu Tang
中科院分区：
文献类型：
--
作者：
Deng Tang;C. Carlet;Xiaohu Tang
受屠和邓的启发，我们提出了两类2k元布尔函数，其中k ≥ 2.第一类包含具有高代数次数和非线性的不平衡函数。第二个函数是平衡的，具有最大代数次数和高非线性（如我们证明的下限所示;作为副产品，我们还证明了Carlet-Feng函数的非线性更好的下限）。由于一个组合的事实，首先由作者证明，后来由科恩和弗洛里证明，我们能够表明，他们都具有最佳的代数免疫。还检查了，至少对于变量数n ≤ 16，这两类函数对快速代数攻击具有良好的行为。与已知的抗代数攻击和快速代数攻击的布尔函数相比，它们都具有最高的非线性度下界。然而，这些界限不足以确保足够的非线性，以允许抵抗快速相关攻击。然而，对于先前发现的具有相同特征的函数，我们可以证明的界限与对有限数量的变量（n ≤ 38）计算的实际值之间存在差距。而且，这些价值观是非常好的。我们在构造2中提出的无限函数类在所有当前已知的构造中呈现了所有重要的密码学标准之间的最佳可证明折衷。
Inspired by the previous work of Tu and Deng, we propose two infinite classes of Boolean functions of 2k variables where k ≥ 2. The first class contains unbalanced functions having high algebraic degree and nonlinearity. The functions in the second one are balanced and have maximal algebraic degree and high nonlinearity (as shown by a lower bound that we prove; as a byproduct we also prove a better lower bound on the nonlinearity of the Carlet-Feng function). Thanks to a combinatorial fact, first conjectured by the authors and later proved by Cohen and Flori, we are able to show that they both possess optimal algebraic immunity. It is also checked that, at least for numbers of variables n ≤ 16, functions in both classes have a good behavior against fast algebraic attacks. Compared with the known Boolean functions resisting algebraic attacks and fast algebraic attacks, both of them possess the highest lower bounds on nonlinearity. These bounds are however not enough for ensuring a sufficient nonlinearity for allowing resistance to fast correlation attack. Nevertheless, as for previously found functions with the same features, there is a gap between the bound that we can prove and the actual values computed for bounded numbers of variables (n ≤ 38). Moreover, these values are very good. The infinite class of functions we propose in Construction 2 presents, among all currently known constructions, the best provable tradeoff between all the important cryptographic criteria.