Non Observability in the Random Oracle Model

The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to

heuristically argue about the security of cryptographic primitives and protocols. The basis

of this heuristic is that secure hash functions are close enough to random functions in their

behavior, and so, a primitive that is secure using a random function should continue to remain secure even when the random function is substituted with a real hash function. In the security proof, this setting is realized by modeling the hash function as a random oracle. However, this approach in particular also enables any reduction, reducing a hard problem to the existence of an adversary, to observe the queries the adversary makes to its random oracle and to program the responses that the oracle provides to these queries. While, the issue of programmability of query responses has received a lot of attention in the literature, to the best of our knowledge, observability of the adversary’s queries has not been identified as an artificial artefact of the Random Oracle Model. In this work, we study the security of several popular schemes when the security reduction cannot “observe” the adversary’s queries to the random oracle, but can (possibly) continue to “program” the query responses. We first show that RSA-PFDH and Schnorr’s signatures continue to remain secure when the security reduction is non observing, which is not surprising as their proofs in the random oracle model rely on programmability.

We provide two example schemes, namely, Fischlin’s NIZK-PoK [Fis05] and non interactive

extractable commitment scheme, extractor algorithms of which seem to rely on observability in the random oracle model. While Fischlin’s online extractors can be proved to not exist when they are non observing, our extractable commitment schemes continues to be secure even when the extractors are non observing. We also introduce non observing non programming reductions which we believe are closest to standard model reductions.


> Publications > Non Observability in the Random Oracle Model