The Best Linear Expression Search of FEAL

Shiho MORIAI  Kazumaro AOKI  Kazuo OHTA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.1   pp.2-11
Publication Date: 1996/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Linear Cryptanalysis,  best linear expression,  FEAL,  search algorithm,  

Full Text: PDF>>
Buy this Article

It is important to find the best linear expression to estimate the vulnerability of cryptosystems to Linear Cryptanalysis. This paper shows the results of the best linear expressions search of FEAL-N (N32) and discusses the security of FEAL against Linear Cryptanalysis. We improve Matsui's search algorithm which determines the best linear expressions, and apply it to FEAL. The improved search algorithm finds all the best linear expression of FEAL-N (N32) much faster than the original; the required time is decreased from over three months to about two and a half days. We find the best linear expressions of FEAL-7, FEAL-15, and FEAL-31 with deviations of 1.152-8, 1.482-20, and 1.992-41, respectively. These linear expressions have higher deviations than those derived from Bi-ham's 4-round iterative linear approximations. Using these data we calculated the number of known plaintexts required to attack FEAL-8, FEAL-16, and FEAL-32. It is proved that FEAL-32 is secure against Linear Cryptanalysis.