Abstract
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. They formally define Non-Observing (NO) reductions and prove which classic schemes, such as Schnorr signatures and RSA-PFDH, remain secure when this power is removed, while identifying others that fundamentally rely on it.
Introduction
In theoretical cryptography, the Random Oracle Model (ROM) is a standard tool used to prove the security of systems. In this model, a hash function is treated as a perfectly random, public box. However, the "reduction"—the mathematical proof that transforms an attack on the scheme into a solution for a hard mathematical problem—is typically granted two artificial powers:
- Programmability: The ability to choose the output of the oracle for a specific input.
- Observability: The ability to see exactly what inputs the adversary is feeding into the oracle.
In the real world (the "Standard Model"), you cannot see what someone is hashing inside their own computer. This paper asks whether observability is an essential crutch for security proofs or if we can construct robust proofs without it.
Defining Non-Observing Reductions
The authors formally define Non-Observing (NO) reductions. In this setup, the adversary and the reduction both interact with an external Random Oracle. Crucially, the reduction never sees the adversary's queries.
To maintain the power of programmability without observability, the reduction programs the oracle by sending it a Turing Machine ($M$) that dictates how to respond to queries. The reduction can update $M$ over time but remains blind to the specific inputs the adversary provides. This setup, visualized in Figure 2, aims to create proofs that are one step closer to the reality of the Standard Model.
They also introduce Non-Observing Non-Programming (NONP) reductions, which they argue represent the closest possible approximation to the Standard Model within the ROM framework.
Key Insights and Methodology
Rewinding without Peeking
A surprising insight of the paper is that "forking" or "rewinding" arguments—essential for proving the security of signatures—can still be performed without knowing what the adversary queried. By providing the oracle with two different lists of responses (via the Turing Machine $M$), 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—fundamentally require observability. For Fischlin’s Non-Interactive Zero-Knowledge (NIZK) scheme, the authors prove that if you cannot see the queries, you simply cannot extract the witness. This confirms that Fischlin's construction relies heavily on the artificial observability of the ROM.
Key Results
- Robustness of Classic Signatures: The authors prove that Schnorr and RSA-PFDH signature schemes remain secure even under Non-Observing reductions. This suggests their security does not 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.
- Extractable Commitments: The authors successfully construct a new 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.
Limitations and Future Work
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 more challenging. Future work may also extend these techniques to create "plaintext-aware" encryption schemes that do not rely on observability for extraction.
Summary updated