黑盒子复杂度之线性度量

The Complexity of Black-box in Term of Linear Span

jakobsen,、kuhdsen利用lagrange插值公式对分组密码给出了一个攻击。该问题可抽象为黑盒子问题即需要多少输入输出可以唯一确定s-盒。该文利用逻辑函数的迹表示给出了s-盒的一种线性复杂度度量。并计算了一些构造性方法构造的逻辑函数的线性复杂度。

jakobsen and Knudsen gave an attack on block cipher with lagrange formula.The problem can be abstracted as a black-box problem:using how many inputs and outputs,the black-box can be uniquely determined.Linear span as a complexity measure of the s-box is given by the trace representation of Boolean functions.The linear span of some Boolean function is computed.