Non Observability in the Random Oracle Model

Prabhanjan Ananth, Raghav Bhaskar

TL;DR

This paper investigates a hidden "superpower" in the Random Oracle Model (ROM): observability. While most cryptographic research focuses on the ability to program hash function outputs, the authors show that simply seeing an adversary's queries is a powerful tool that doesn't exist in the real world, and they prove which classic schemes (like Schnorr signatures) survive when this power is taken away.

What Problem Does This Paper Address?

In theoretical cryptography, we often prove a system is secure using the Random Oracle Model (ROM). In this model, we pretend a hash function is a perfectly random, public box. However, the "reduction"—the mathematical proof that turns an attack on the scheme into a solution for a hard math problem—gets two artificial powers:

  1. Programmability: The ability to choose what the box outputs for a specific input.
  2. Observability: The ability to see exactly what inputs the adversary is feeding into the box.

In the real world (the "Standard Model"), you can't see what someone is hashing inside their own computer. This paper asks: Is observability an essential crutch for our security proofs, or can we do without it? By stripping away observability, the authors aim to create proofs that are one step closer to the reality of the Standard Model.

Methods

The authors formally define Non Observing (NO) reductions. In this setup:

  • The adversary and the reduction both talk to an external Random Oracle.
  • The reduction can still "program" the oracle by sending it a Turing Machine ($M$) that dictates how to respond to queries.
  • Crucially, the reduction never sees the adversary's queries. It only knows that some query was made and provides a rule for the response.

They also introduce Non Observing Non Programming (NONP) reductions, which they argue are the closest possible approximation to the Standard Model within the ROM framework.

To test these definitions, they re-examine classic constructions:

  • Signatures: They analyze RSA-PFDH and Schnorr signatures.
  • NIZKs: They look at Fischlin’s Non-Interactive Zero-Knowledge Proofs of Knowledge (NIZK-PoK).
  • Commitments: They design a new extractable commitment scheme specifically to work without observability.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, it relies on mathematical proofs and complexity-theoretic assumptions (like the Discrete Log Problem and RSA Inversion) rather than empirical datasets.

Key Insights and Ideas

  • Rewinding without Peeking: The most surprising insight is that you can still perform a "forking" or "rewinding" argument (essential for proving signature security) without knowing what the adversary queried. By providing the oracle with two different lists of responses, the reduction can force a "fork" in the adversary's execution blindly.
  • The Necessity of Sight for Online Extraction: The paper reveals that "online extractors"—algorithms that extract a secret witness from a proof without rewinding the adversary—seem to fundamentally require observability. They prove that for Fischlin’s NIZK scheme, if you can't see the queries, you simply cannot extract the witness.
  • Observability is an Artificial Artifact: The authors argue that while programmability has been debated for decades, observability is an equally "unreasonable" ability that provides the challenger with information they would never have in a real-world black-box setting.

Key Results

  • Schnorr and RSA-PFDH are Robust: The authors prove that these widely-used signature schemes remain secure even under Non Observing reductions. This suggests their security doesn't rely on the "unrealistic" power of seeing an adversary's private hashes.
  • Fischlin’s Impossibility: They provide a formal proof that Non Observing online extractors for Fischlin’s NIZK-PoK cannot exist. This confirms that Fischlin's construction relies heavily on the "artificial" observability of the ROM.
  • A New Commitment Scheme: They successfully construct an extractable commitment scheme ($ExtCom$) that remains secure even when the extractor is non-observing. This proves that "extraction" (recovering a committed value) is possible through programming alone, without needing to see the committer's queries.

Limitations and Future Work

  • The Gap to the Standard Model: While NO reductions are "closer" to the standard model, they still allow for programming. The authors note that Non Observing Non Programming (NONP) reductions are the ultimate goal, but proving security in that model is significantly harder.
  • Extension to Encryption: The authors briefly mention that their techniques for extractable commitments could be extended to create "plaintext-aware" encryption schemes with non-observing extractors, but they leave the full formalization for future research.
  • Scope of Schemes: The paper focuses on a few specific (though popular) primitives. It remains to be seen how many other ROM-based protocols rely on observability as a "hidden" requirement.

Summary updated

BibTeX
@inproceedings{ananth2013non,
  author = {Prabhanjan Ananth and Raghav Bhaskar},
  title = {{Non Observability in the Random Oracle Model}},
  booktitle = {ProvSec},
  year = {2013},
  doi = {10.1007/978-3-642-41227-1\_5},
}
Figure