TAILIEUCHUNG - The Random Oracle Methodology, Revisited

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called \cryptographic hash functions". The main result of this paper is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible denitions for the notion of a good implementation" of a random oracle, pointing out limitations and challenges. | The Random Oracle Methodology Revisited Ran Canettiy Oded Goldreichz Shai Halevi x August 6 2002 Abstract We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model and the security of the schemes that result from implementing the random oracle by so called cryptographic hash functions . The main result of this paper is a negative one There exist signature and encryption schemes that are secure in the Random Oracle Model but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes we consider possible definitions for the notion of a good implementation of a random oracle pointing out limitations and challenges. Keywords Correlation Intractability Cryptography Encryption and Signature Schemes The Random Oracle model Complexity Theory diagonalization application of CS-Proofs . Extended abstract has appeared in the Proc. of the 30th ACM Symp. on Theory of Computing STOC pages 209-218 1998. yIBM Watson . Box 704 Yorktown Height NY 10598 USA. E-mail canetti@ Department of Computer Science Weizmann Institute of Science Rehovot Israel. E-mail oded@. Work done while visiting LCS MIT. Partially supported by DARPA grant DABT63- 96-C-0018. xIBM Watson . Box 704 Yorktown Height NY 10598 USA. E-mail shaih@ 1 Contents 1 Introduction 2 The Setting. 2 The Random Oracle Model. 3 Implementing an ideal system. 3 Our Results. 5 Correlation intractability . 5 Failures of the Random Oracle Methodology . 6 Techniques . 7 Related Work. 7 Previous Work. 7 Subsequent Work. 7 Organization . 9 2 Preliminaries 9 Function Ensembles . 9 CS Proofs. 10 3 Correlation Intractability 12 Actual Definitions . 12 Correlation-intractable ensembles do not exist. 13 4 Failures of the Random Oracle Methodology 14 First Step . 15 Second Step . 17 .

• Công nghệ thông tin
• Random Oracle (RO) model
• Failures of the Random Oracle Methodology
• The Random Oracle Model
• Implementing an ideal system
• Correlation intractable ensembles
• The Random Oracle Methodology
• Attack of Luby Rackoff with 5 Rounds
• Simulator’s Running Time
• The Ideal Cipher Model
• The Cipher Model
• Random oracle model
• Theoretical foundations of cryptography
• Looking ahead
• Signature scheme in the RO model