Algebraic Attack on Boolean Functions

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.