布尔函数的代数攻击

Algebraic Attack on Boolean Functions

  • 摘要: 基于代数攻击,提出了一种已知部分真值表还原整个布尔函数的方法。对于n元d次布尔函数, 该方法的空间复杂度和数据复杂度均为O(N),计算复杂度为O(N3),其中N=1+C1n+C2n+…+Cdn。由复杂度可知,所求密码函数的代数次数越低,该方法的有效性越高。攻击方法表明密码设计中应该谨慎使用代数次数较低的布尔函数。

     

    Abstract: Based on algebraic attack, a new reconstruction method of Boolean functions from the partial truth table is proposed. For the Boolean function with n variables and the degree of d, the proposed method requires O(N) values in the truth table, and the computational complexity is O(N3), and the memory complexity is O(N), where N=1+C1n+C2n+…+Cdn. From the above complexity, the lower the degree of the Boolean function is,the more efficient the method is. The proposed attack shows the designer of stream cipher should use Boolean functions with low degree carefully.

     

/

返回文章
返回