Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOM ORACLE MODEL:
Reports tagged with Random oracle model:
TR03-015 | 20th March 2003
Yael Tauman Kalai

On the (In)security of the Fiat-Shamir Paradigm

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>


TR12-065 | 16th May 2012
Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

Limits of Random Oracles in Secure Computation

Revisions: 2

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for ... more >>>


TR23-137 | 10th September 2023
Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments

Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be ... more >>>




ISSN 1433-8092 | Imprint