Paper 2008/246

The Random Oracle Model and the Ideal Cipher Model are Equivalent

Jean-Sebastien Coron, Jacques Patarin, and Yannick Seurin

Abstract

The Random Oracle Model and the Ideal Cipher Model are two well known idealised models of computation for proving the security of cryptosystems. At Crypto 2005, Coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. The other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. In this paper we solve this open problem and show that the Feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. This contrasts with the classical Luby-Rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. An extended abstract of this paper will appear at CRYPTO 2008. This is the full version.
Keywords
random oracle modelideal cipher modelindifferentiabilityFeistelLuby-Rackoff construction.
Contact author(s)
jscoron @ gmail com
History
2008-08-16: revised
2008-06-03: received
See all versions
Short URL
https://ia.cr/2008/246
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/246,
      author = {Jean-Sebastien Coron and Jacques Patarin and Yannick Seurin},
      title = {The Random Oracle Model and the Ideal Cipher Model are Equivalent},
      howpublished = {Cryptology ePrint Archive, Paper 2008/246},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/246}},
      url = {https://eprint.iacr.org/2008/246}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.