Under a random oracle, a countable family of infinite languages has closure dimension zero and admits zero-mistake unbounded generation, yet every polynomial-query generator incurs an exponential expected-mistake lower bound on some target.
The Random Oracle Methodology, Revisited
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.CC 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation
Under a random oracle, a countable family of infinite languages has closure dimension zero and admits zero-mistake unbounded generation, yet every polynomial-query generator incurs an exponential expected-mistake lower bound on some target.