Abstract
In this paper we are dealing with the security of the Feistel structure in the Luby–Rackoff model when the round functions are replaced by permutations. There is a priori no reason to think that the security bounds remain the same in this case, as illustrated by Knudsen’s attack [5]. It is why we revisit Luby–Rackoff’s proofs [6] in this specific case. The conclusion is that when the inner functions are random permutations, a 3-round (resp. 4-round) Feistel scheme remains secure against pseudorandom (resp. superpseudorandom) distinguishers as long as m 
2n/2 (with m the number of queries and 2n the block size).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Aoki, T. Ichikawa, M. Kanda, M.Matsui S. Moriai, J. Nakajima and T.Tokita, Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms—Design and Analysis. In D.R. Stinson and S.E. Tavares (eds.), Selected Areas in Cryptography, 7th Annual International Workshop, SAC 2000, Waterloo, Canada, August 14–15, 2000, volume 2012 of Lecture Notes in Computer Science, Springer-Verlag (2001) pp. 39–56.
K. Aoki K. Ohta (1997) ArticleTitleStrict evaluation for the maximum average of differential probability and the maximum average of linear probability IEICE Transactions on Fundamentals E80-A 2–8
E. Biham, Cryptanalysis of Ladder-DES. In Eli Biham (ed.), Fast Software Encryption, Haifa, Israel, January 20–22, 1997, volume 1267 of Lecture Notes in Computer Science, Springer-Verlag (1997) pp. 134–138.
H. Gilbert and M. Minier, New results on the pseudorandomness of some blockcipher constructions, In Mitsuru Matsui, editor, Fast Software Encryption,Yokohama, Japan, April 2–4, 2001, volume 2355 of Lecture Notes in Computer Science, Springer-Verlag (2002) pp. 248–266.
L. R. Knudsen, DEAL – A 128-bit Block Cipher, Technical Report #151, University of Bergen, Department of Informatics, Norway, February 1998. Submitted as a candidate for the Advanced Encryption Standard.
M. Luby C. Rackoff (1998) ArticleTitleHow to construct pseudorandom permutations from pseudorandom functions SIAM Journal on Computing 17 IssueID2 373–386 Occurrence Handle89i:68025
S. Lucks, Faster Luby–Rackoff ciphers, In Dieter Gollmann (ed.), Fast Software Encryption, Cambridge, UK, February 21–23, 1996, volume 1039 of Lecture Notes in Computer Science, Springer-Verlag (1996) pp. 189–203.
M. Naor O. Reingold (1999) ArticleTitleOn the construction of pseudorandom permutations: Luby–Rackoff Revisited Journal of Cryptology 12 IssueID1 29–66 Occurrence Handle2000k:94035
K. Nyberg, Linear approximation of block ciphers. In Alfredo De Santis (ed.), Advances in Cryptology—EUROCRYPT ’94, Perugia, Italy, May 9–12, 1994, volume 950 of Lecture Notes in Computer Science, Springer-Verlag (1995) pp. 439–444.
K. Nyberg L. R. Knudsen (1995) ArticleTitleProvable security against differential cryptanalysis Journal of Cryptology 8 IssueID1 27–37 Occurrence Handle10.1007/BF00204800 Occurrence Handle95m:94007
J. Patarin, Etude des Générateurs de Permutations Basés sur le Schéma du DES. PhD thesis, Université Paris VI, November 1991.
J. Patarin, How to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function. In Rainer A. Rueppel (ed.), Advances in Cryptology—EUROCRYPT ’92, Balatonfüred, Hungary, May 24–28, 1992, volume 658 of Lecture Notes in Computer Science, Springer-Verlag (1993) pp. 256–266.
J. Patarin, About Feistel schemes with six (or more) rounds. In Serge Vaudenay (ed.), Fast Software Encryption, Paris, France, March 23–25, 1998, volume 1372 of Lecture Notes in Computer Science, Springer-Verlag (1998) pp. 103–121.
J. Patarin, Generic attacks on Feistel schemes. In Colin Boyd (ed.), Advances in Cryptology – ASIACRYPTM 2001, Gold Coast, Australia, December 9–13, 2001, volume 2248 of Lecture Notes in Computer Science, Springer-Verlag (2001) pp. 222–238.
J. Patarin, Luby-Rackoff: 7 Rounds are enough for 2n(1−ε) security. In Dan Boneh (ed.), Advances in Cryptology – CRYPTO 2003, Santa Barbara, USA, August 17–21, 2003, volume 2729 of Lecture Notes in Computer Science, Springer-Verlag (2003) pp. 513–529.
J. Patarin, Security of random feistel schemes with 5 or more rounds. In Matt Franklin (ed.), Advances in Cryptology – CRYPTO 2004, Santa Barbara, USA, August 15–19, 2004, volume 3152 of Lecture Notes in Computer Science, Springer-Verlag (2004) pp. 106–122.
Z. Ramzan and L. Reyzin, On the round security of symmetric-key cryptographic primitives. In Mihir Bellare (ed.), Advances in Cryptology – CRYPTO 2000, Santa Barbara, USA, August 20–24, 2000, volume 1880 of Lecture Notes in Computer Science, Springer-Verlag (2000) pp. 376–393.
V. Rijmen B. Preneel E. Win ParticleDe (1997) ArticleTitleOn weaknesses of non-surjective round functions Designs, Codes and Cryptography 12 IssueID3 253–266 Occurrence Handle10.1023/A:1008224928678 Occurrence Handle98e:94022
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall and N. Ferguson Twofish: A 128-bit Block Cipher. NIST AES Proposal. Available from http://www.counterpane.com/twofish.html, June 1998.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: A. J. Menezes
The main part of this work was carried out when the author was a member of the UCL Crypto Group (http://www.uclcrypto.org).
Rights and permissions
About this article
Cite this article
Piret, G. Luby–Rackoff Revisited: On the Use of Permutations as Inner Functions of a Feistel Scheme. Des Codes Crypt 39, 233–245 (2006). https://doi.org/10.1007/s10623-005-3562-2
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-005-3562-2