TAILIEUCHUNG - The Random Oracle Model and the Ideal Cipher Model are Equivalent

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. | The Random Oracle Model and the Ideal Cipher Model are Equivalent Jean-Sebastien Coron1 Jacques Patarin2 and Yannick Seurin2 3 1 University of Luxembourg 2 University of Versailles 3 Orange Labs 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 . 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. 1 Introduction Modern cryptography is about defining security notions and then constructing schemes that provably achieve these notions. In cryptography security proofs are often relative a scheme is proven secure assuming that some computational problem is hard to solve. For a given functionality the goal is therefore to obtain an efficient scheme that is secure under a well known computational assumption for example factoring is hard . However for certain functionalities or to get a more efficient scheme it is sometimes necessary to work in some idealised model of computation. The well known Random Oracle Model ROM formalised by Bellare and Rogaway 1 is one such model. In the random oracle model one assumes that some hash function is replaced by a publicly accessible random function the random oracle . This means that the adversary cannot compute the result of the hash .

• Cơ sở dữ liệu
• The Random Oracle Model
• Random Oracle (RO) model
• Attack of Luby Rackoff with 5 Rounds
• Simulator’s Running Time
• The Ideal Cipher Model
• The Cipher Model
• Failures of the Random Oracle Methodology
• Implementing an ideal system
• Correlation intractable ensembles
• The Random Oracle Methodology
• Random oracle model
• Theoretical foundations of cryptography
• Looking ahead
• Signature scheme in the RO model
• Public key encryption algorithm
• Random oracle
• Black box that responds
• Cryptographic practice
• A Paradigm for Designing Efficient Protocols
• Designing Efficient Protocols
• Random oracle paradigm
• Chosen Cipher text Security
• A digital signature scheme
• Digital signature
• Digital signature schemes
• Random oracles
• Constructions based on bilinear maps
• Design and Analysis of Algorithms
• Analysis of Algorithms
• Design of Algorithms
• Data structures
• Linear programming
• Hash functions
• Cryptography & Network Security
• Cryptography & Network Security Exercise
• Symmetric Cipher Model
• Classical Substitution Ciphers
• Cryptanalysis using letter frequencies
• Polyalphabetic Ciphers
• Double block length compression function
• Collision security
• Preimage security
• Ideal cipher model
• Definition of Alpha DBL scheme