布尔函数的代数攻击 (2010年)

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