A linear equivalence algorithm

Year, pages: 2007, 113 - 122

J. Fuller and W. Millan in: [ extit{Linear redundancy in S-boxes}. In: FSE~'03 (T.~Johansson, ed.), Lect. Notes Comput. Sci., Vol. 2887, Springer-Verlag, Berlin, 2003, pp.~74--86] proved that coordinate Boolean functions of the AES s-box are linearly equivalent. Although to this time no one described the attack based on this observation, we believe that it affects the complexity of the cryptographic attack on AES. Therefore, a fast algorithm for testing if two Boolean functions are linearly equivalent can be very useful when designing and analyzing S-boxes. In this contribution we present a new algorithm for solving this task. Our algorithm not only tests if two Boolean functions are linearly equivalent but also creates, if it is possible, a matrix which establishes a linear equivalence for considered functions.

Serweciński, M. 2007. A linear equivalence algorithm. In Tatra Mountains Mathematical Publications, vol. 37, no.3, pp. 113-122. 1210-3195.

Serweciński, M. (2007). A linear equivalence algorithm. Tatra Mountains Mathematical Publications, 37(3), 113-122. 1210-3195.