How to search linear approximation for large non-surjective S-box

Linear cryptanalysis is a general form of cryptanalysis based on identifying the linear approximations of a cipher. It is one of the two most widely used attacks on block ciphers. In order to resist the differential cryptanalysis, the S-box with large output bit number is applied in block cipher, for example CAST-128 and CAST-256 use the 8 × 32 S-boxes. In addition, the S-boxes are often constructed based on bent functions to resist the linear cryptanalysis and the S-boxes are non-surjective mapping. Therefore, for the large non-surjective S-box, to identify the best linear approximation with zero input mask and nonzero output mask is difficult due to the unaccepted computation time. In this paper, we will give an efficient computing method to find such best linear approximations for the non-surjective large S-boxes using parallel computation in practical time. This computing method can help to estimate the resistant property for some kind of linear cryptanalysis of block ciphers with this kind of S-box.