Abstract
We show that there exists a natural protocol problem which has a simple solution in the random-oracle (RO) model and which has no solution in the complexity-theoretic (CT) model, namely the problem of constructing a non-interactive communication protocol secure against adaptive adversaries a.k.a. non-interactive non-committing encryption. This separation between the models is due to the so-called programability of the random oracle. We show this by providing a formulation of the RO model in which the oracle is not programmable, and showing that in this model, there does not exist non-interactive non-committing encryption.
Basic Research in Computer Science, Centre of the Danish National Research Foundation.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Beaver. Plug and play encryption. In Crypto’ 97, pages 75–89, Berlin, 1997. Springer. LNCS Vol. 1294.
Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In [ACM88], pages 103–112.
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In [ACM88], pages 1–10.
D. Beaver and S. Haber. Cryptographic protocols provably secure against dynamic adversaries. In EuroCrypt’ 92, pages 307–323, Berlin, 1992. Springer. LNCS Vol. 658.
Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In First ACM Conference on Computing and Communications Security, pages 62–73. ACM, 1993.
M. Bellare and P. Rogaway. Optimal asymmetric encryption. In EuroCrypt’94, pages 92–111, Berlin, 1995. Springer. LNCS Vol. 950.
Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, winter 2000.
Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42th Annual Symposium on Foundations of Computer Science. IEEE, 2001.
David Chaum, Claude Crépeau, and Ivan Damgøard. Multiparty unconditionally secure protocols (extended abstract). In [ACM88], pages 11–19.
Ran Canetti, Uri Feige, Oded Goldreich, and Moni Naor. Adaptively secure multi-party computation. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 639–648, Philadelphia, Pennsylvania, 22–24 May 1996.
Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited (preliminary version). In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 209–218, Dallas, TX, USA, 24–26 May 1998.
Ivan Damgøard and Jesper B. Nielsen. Improved non-committing encryption schemes based on a general complexity assumption. In Crypto 2000, pages 432–450, Berlin, 2000. Springer. LNCS Vol. 1880.
A. Fiat and A. Shamir. How to prove yourself: practical solutions to identification and signature problems. In Crypto’ 86, pages 186–194, Berlin, 1986. Springer. LNCS Vol. 263.
O. Goldreich and H. Krawczyk. On the composition of zero knowledge proof systems. In Proceedings of ICALP 90, Berlin, 1990. Springer. LNCS Vol. 443.
Victor Shoup. OAEP reconsidered. In Crypto 2001, pages 239–259, Berlin, 2001. Springer. LNCS Vol. 2139.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nielsen, J.B. (2002). Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_8
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive