Abstract: The complexity and the degree of the algebraic expression for the Sbox are symbols of resistance of block ciphers against the interpolation attacks. The algebraic expression for the Rijndael Sbox has a high degree of 254 but low complexity that only nine items are there. We have investigated a new property of the finite field that the component of the field element can be expressed by a simple polynomial with the element itself as the variable. Then a new method to determine the algebraic expression for the Rijndael Sbox is proposed. Conclusions are drawn and proved that the low complexity of the algebraic expression for the Rijndael Sbox is mainly caused by the binary matrix in the construction of the Sbox and that any other choice of teh generating polynomial, the affine matrix or the affine constant will not make the expression more complex. Finally, the quideline for improvement is pointed out.

Key words: AES, Sbox, interpolation attacks, finite field, algebraic expression