2010/11/04 by Thomas Holenstein, Holenstein, Thomas, Robin Künzler +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chaos-based Image/Signal Encryption #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #Cryptography and Data Security #Cryptography and Security (cs.CR) #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1011.1264
openalex publication_date 2010/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the cryptographic problem of constructing an invertible random\npermutation from a public random function (i.e., which can be accessed by the\nadversary). This goal is formalized by the notion of indifferentiability of\nMaurer et al. (TCC 2004). This is the natural extension to the public setting\nof the well-studied problem of building random permutations from random\nfunctions, which was first solved by Luby and Rackoff (Siam J. Comput., '88)\nusing the so-called Feistel construction.\n The most important implication of such a construction is the equivalence of\nthe random oracle model (Bellare and Rogaway, CCS '93) and the ideal cipher\nmodel, which is typically used in the analysis of several constructions in\nsymmetric cryptography.\n Coron et al. (CRYPTO 2008) gave a rather involved proof that the six-round\nFeistel construction with independent random round functions is\nindifferentiable from an invertible random permutation. Also, it is known that\nfewer than six rounds do not suffice for indifferentiability. The first\ncontribution (and starting point) of our paper is a concrete distinguishing\nattack which shows that the indifferentiability proof of Coron et al. is not\ncorrect. In addition, we provide supporting evidence that an\nindifferentiability proof for the six-round Feistel construction may be very\nhard to find.\n To overcome this gap, our main contribution is a proof that the Feistel\nconstruction with eigthteen rounds is indifferentiable from an invertible\nrandom permutation. The approach of our proof relies on assigning to each of\nthe rounds in the construction a unique and specific role needed in the proof.\nThis avoids many of the problems that appear in the six-round case.\n