Universite Bordeaux 1
In this paper, the authors first present a modification of matsui's branch-and-bound algorithm for the linear approximation search in a block cipher. It enabled the authors to find the best reported 9-round approximation for the AES candidate Serpent. The algorithm allows speeding up the search of linear approximations at the cost of larger memory requirements. It is generic and especially well suited for ciphers where the linear transformation involves an important avalanche effect (as the AES candidates and most recent ciphers). Moreover, it could be straightforwardly adapted for the research of differential characteristics.