Aarhus University Seal

Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-Committing Encryption Case

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationAdvances in Cryptology — CRYPTO 2002 : 22nd Annual International Cryptology Conference Santa Barbara, California, USA, August 18–22, 2002 Proceedings
EditorsMoti Yung
Number of pages23
Publication year2002
ISBN (print)978-3-540-44050-5
Publication statusPublished - 2002
EventCRYPTO 2002 - Santa Barbara, California, United States
Duration: 18 Aug 200222 Aug 2002
Conference number: 22


ConferenceCRYPTO 2002
LandUnited States
BySanta Barbara, California
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 283055