Algebraic Attacks and Decomposition of Boolean Functions
Algebraic Attacks and Decomposition of Boolean Functions
复制标题
DOI：
10.1007/978-3-540-24676-3_28
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
W. Meier;E. Pasalic;C. Carlet
中科院分区：
文献类型：
--
作者：
W. Meier;E. Pasalic;C. Carlet
对基于LFSR的流密码的代数攻击通过求解一个超定义的多变量代数方程组来恢复密钥。它们利用了涉及密钥位和输出位的多变量关系，如果可以找到这种低次关系，则会变得非常有效。已经证明，对于免疫所有已知攻击的几种众所周知的流密码构造，存在低度关系。这种关系可以通过将流密码的输出函数乘以精心选择的低次函数来导出，使得乘积函数再次是低次的。针对代数攻击，布尔函数的低次倍数是流密码和分组密码设计中的一个基本问题，研究了布尔函数在几个方向上的低次倍数的存在性：将存在低次倍数的已知场景简化为两种场景，在代数攻击中对这两种场景进行不同的处理。提出了一种新的判定布尔函数是否具有低次倍数的算法。这代表着朝着针对代数攻击的可证明安全性迈出了重要的一步。此外，还证明了最近引入的一类次数优化的Maiorana-McFarland函数内在地具有低次倍数。最后，对随机布尔函数具有低次倍数的概率进行了估计。
Algebraic attacks on LFSR-based stream ciphers recover the secret key by solving an overdefined system of multivariate algebraic equations. They exploit multivariate relations involving key bits and output bits and become very efficient if such relations of low degrees may be found. Low degree relations have been shown to exist for several well known constructions of stream ciphers immune to all previously known attacks. Such relations may be derived by multiplying the output function of a stream cipher by a well chosen low degree function such that the product function is again of low degree. In view of algebraic attacks, low degree multiples of Boolean functions are a basic concern in the design of stream ciphers as well as of block ciphers.This paper investigates the existence of low degree multiples of Boolean functions in several directions: The known scenarios under which low degree multiples exist are reduced and simplified to two scenarios, that are treated differently in algebraic attacks. A new algorithm is proposed that allows to successfully decide whether a Boolean function has low degree multiples. This represents a significant step towards provable security against algebraic attacks. Furthermore, it is shown that a recently introduced class of degree optimized Maiorana-McFarland functions immanently has low degree multiples. Finally, the probability that a random Boolean function has a low degree multiple is estimated.