A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma

Matsui’s linear cryptanalysis for iterated block ciphers is generalized by replacing his linear expressions with I/O ssons sums. For a single round, an I/O sum is the XOR of a balanced binary-valued func- tion of the round input and a balanced binary-valued function of the round output. The basic attack is described and conditions for it to be successful are given. A procedure for finding effective I/O sums, i.e., I/O sums yielding successful attacks, is given. A cipher contrived to be se- cure against linear cryptanalysis but vulnerable to this generalization of linear cryptanalysis is given. Finally, it is argued that the ciphers IDEA and SAFER K-64 are secure against this generalization.