Security Analysis of Key-Alternating Feistel Ciphers

International audienceWe study the security of key-alternating Feistel ciphers, a class of key-alternating ciphers with a Feistel structure. Alternatively, this may be viewed as the study of Feistel ciphers where the pseudorandom round functions are of the form F-i(x circle plus k(i)), where k(i) is the (secret) round key and F-i is a public random function that the adversary is allowed to query in a black-box way. Interestingly, our results can be seen as a generalization of traditional results a la Luby-Rackoff in the sense that we can derive results for this model by simply letting the number of queries of the adversary to the public random functions F-i be zero in our general bounds. We make an extensive use of the coupling technique. In particular (and as a result of independent interest), we improve the analysis of the coupling probability for balanced Feistel schemes previously carried out by Hoang and Rogaway (CRYPTO 2010)