An Infinite Class of Balanced Functions with Optimal Algebraic Immunity, Good Immunity to Fast Algebraic Attacks and Good Nonlinearity
An Infinite Class of Balanced Functions with Optimal Algebraic Immunity, Good Immunity to Fast Algebraic Attacks and Good Nonlinearity
复制标题
DOI：
10.1007/978-3-540-89255-7_26
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
C. Carlet;K. Feng
中科院分区：
文献类型：
--
作者：
C. Carlet;K. Feng
在Courtois和Meier对流密码的代数攻击进行改进并引入代数免疫的相关概念之后，提出了几种具有最佳代数免疫的无限类布尔函数的构造。它们都给出了代数度足够高的函数，足以抵抗 Berlekamp-Massey 攻击和最近的 Rønjom-Helleseth 攻击，但其非线性要么达到最差的可能值（由 Lobanov 界给出），要么稍优于它。因此，这些函数无法抵抗快速关联攻击。此外，它们在快速代数攻击方面表现不佳。在本文中，我们研究了实现最佳代数免疫性的无限类函数。我们证明它们比所有先前获得的无限类函数具有最佳代数次数和更好的非线性。我们检查发现，至少对于变量数量较小的值，此类函数实际上具有非常好的非线性，并且对于快速代数攻击也具有良好的行为。
After the improvement by Courtois and Meier of the algebraic attacks on stream ciphers and the introduction of the related notion of algebraic immunity, several constructions of infinite classes of Boolean functions with optimum algebraic immunity have been proposed. All of them gave functions whose algebraic degrees are high enough for resisting the Berlekamp-Massey attack and the recent Rønjom-Helleseth attack, but whose nonlinearities either achieve the worst possible value (given by Lobanov’s bound) or are slightly superior to it. Hence, these functions do not allow resistance to fast correlation attacks. Moreover, they do not behave well with respect to fast algebraic attacks. In this paper, we study an infinite class of functions which achieve an optimum algebraic immunity. We prove that they have an optimum algebraic degree and a much better nonlinearity than all the previously obtained infinite classes of functions. We check that, at least for small values of the number of variables, the functions of this class have in fact a very good nonlinearity and also a good behavior against fast algebraic attacks.