Interactive proof systems allow a prover to convince a verifier of a mathematical statement's validity through a back-and-forth dialogue. While interaction provides strong information-theoretic security guarantees, it requires both parties to be online simultaneously and limits verification to a single, active participant. To make proofs reusable, publicly verifiable, and efficient enough for distributed systems, cryptography relies on non-interactive transformations.
The core mechanism behind this shift is the Fiat-Shamir transform, which replaces a live verifier with a cryptographic hash function. However, removing interaction introduces profound security challenges: the loss of information-theoretic security, the risk of provers "grinding" for favorable challenges, and the threat of adversaries tampering with static proofs.
Eliminating Interaction via Hashing
In a standard three-round interactive proof (often called a $\Sigma$-protocol), the prover sends an initial commitment, the verifier responds with a random challenge, and the prover replies with a response that binds the commitment to the secret witness.
The Fiat-Shamir heuristic eliminates the verifier's active role by forcing the prover to compute the challenge locally. The prover passes the statement and their initial commitment through a cryptographic hash function to generate the challenge. Because a secure hash function's output is unpredictable, the prover cannot anticipate the challenge before fixing their commitment. This forces the prover to act honestly, exactly as if an independent verifier were generating random numbers on the fly.
This basic three-round structure acts as a foundational bridge between interactive and non-interactive paradigms. For example, Bruce M. Kapron et al. leverage this architecture in A Framework for Non-Interactive Instance-Dependent Commitment Schemes (NIC) to transform interactive proof systems into static commitments.
Removing interaction drastically reduces network overhead. As Ioannis Chatzigiannakis et al. demonstrate in Elliptic Curve Based Zero Knowledge Proofs and Their Applicability on Resource Constrained Devices, this reduction in communication is vital for deploying zero-knowledge proofs on resource-constrained Internet of Things (IoT) devices. Furthermore, the resulting non-interactive proofs can be repurposed as standalone digital signatures. Melissa Chase et al. apply this in Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives to construct post-quantum signatures entirely from symmetric-key primitives.
To unify the diverse ways this heuristic is applied across different protocols, Matilda Backendal et al. introduced a generalized framework (gFS) in The Fiat-Shamir Zoo: Relating the Security of Different Signature Variants, mapping how security properties transfer across various hash models and signing strategies. This formalization is necessary because the transform fundamentally shifts the protocol's security: as noted by Kang Yang et al. in QuickSilver: Efficient and Affordable Zero-Knowledge Proofs for Circuits and Polynomials over Any Field, replacing a truly random verifier with a hash function shifts the security guarantee from information-theoretic to computational.
Scaling to Multi-Round Protocols
While three-round protocols map cleanly to a single hash evaluation, modern zero-knowledge applications—such as verifiable computation and memory arithmetization—rely on complex, multi-round interactions. For instance, Alex Ozdemir et al. in Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs utilize multi-round algebraic interactive proofs to handle persistent memory operations before compressing them into non-interactive proofs.
When applying the Fiat-Shamir transform to a protocol with many rounds, a malicious prover gains a new advantage: grinding. If the prover dislikes a hash output in round 4, they can go back to round 3, alter their message slightly, and generate a completely new hash for round 4. In a protocol with many rounds, this trial-and-error strategy could allow a cheating prover to find a path of "lucky" challenges that validates a false statement.
To prevent grinding, multi-round transformations require a property known as round-by-round soundness. As explained by Ran Canetti et al. in Fiat-Shamir From Simpler Assumptions, a protocol exhibits round-by-round soundness if a prover who makes a false claim at any given step enters a "dead end" state. Once the prover lies, the mathematical constraints of the protocol ensure that virtually no hash output can rescue them in subsequent rounds. This prevents the prover from successfully grinding through alternative histories.
Despite its utility, proving the security of non-interactive multi-round protocols remains a significant theoretical hurdle. Binyi Chen notes in LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems that while interactive folding schemes are well-understood, providing rigorous security proofs for their non-interactive, Fiat-Shamir-transformed counterparts remains an open challenge.
Escaping the Random Oracle Fantasy
The classic security proofs for the Fiat-Shamir transform rely on the Random Oracle Model (ROM), an idealized mathematical abstraction where the hash function is treated as a perfectly random, black-box oracle. In the real world, however, hash functions are concrete, deterministic algorithms. A clever adversary might exploit the internal algebraic structure of a real hash function (like SHA-3 or Keccak) to bypass the security guarantees proven in the ROM.
To ground the Fiat-Shamir transform in the "plain model" (using standard, falsifiable cryptographic assumptions), researchers have developed alternative methods for generating challenges.
- Obfuscated Hash Functions: Guy N. Rothblum et al. achieved a breakthrough in From Obfuscation to the Security of Fiat-Shamir for Proofs by using Indistinguishability Obfuscation (iO). By mathematically "scrambling" the code of an input-hiding hash function, they proved that the transform can securely eliminate interaction for constant-round proofs without relying on random oracles.
- Correlation Intractability: Another approach involves designing hash functions that are explicitly correlation-intractable. As detailed by Ran Canetti et al. in Triply Adaptive UC NIZK, a correlation-intractable hash function makes it computationally impossible for an adversary to find an input $x$ such that the output $H(x)$ lands in a specific "cheating relation." This allows for non-interactive proofs that remain secure even if an adversary chooses their statement adaptively after seeing the public parameters.
- Encrypted Challenges in a CRS: Rather than using a hash function to generate challenges dynamically, the verifier's challenges can be pre-computed. Guy N. Rothblum et al. demonstrate in Publicly Verifiable Non-Interactive Arguments for Delegating Computation that challenges can be embedded as encrypted encodings within a Common Reference String (CRS). The prover computes the proof entirely within the encrypted domain, allowing static verification of sequential computations, such as the iterated squaring sequences analyzed by Arka Rai Choudhuri et al. in PPAD-Hardness via Iterated Squaring Modulo a Composite.
The Threat of Malleability
When a proof is compressed into a static string of bits, it becomes vulnerable to malleability attacks. In an interactive setting, the verifier is guaranteed that the prover is actively participating in real time. In a non-interactive setting, an adversary can intercept a valid proof string, alter its bits slightly, and forge a new, valid proof for a related statement—all without knowing the underlying secret witness.
As Michael Backes et al. argue in Computational soundness of symbolic zero-knowledge proofs, standard zero-knowledge definitions only guarantee that a proof doesn't leak secrets; they do not guarantee that the prover actually knows the secret. To prevent adversaries from intercepting and modifying proofs, a system must achieve witness extractability—a mathematical guarantee that any party capable of producing a valid proof must possess the underlying witness.
Without non-malleability, secure concurrent communication is impossible. In network protocols like those studied by Andrew C Yao et al. in Deniable Internet Key-Exchange, an attacker could intercept an authentication proof from one session and relay a modified version to hijack a concurrent session.
To solve this, protocols must achieve simulation-extractability. This property ensures that even if an adversary observes many valid proofs (or simulated proofs), any new proof they generate can be decoded by an extractor to reveal a valid witness. If the adversary tries to copy or tweak an existing proof, the extraction mechanism fails unless they genuinely know the new witness.
[Intercepted Proof] ---> (Adversary Tweaks Bits) ---> [New Malleable Proof]
|
(Simulation Extractor)
|
V---------------------------------V
| Does Adversary Know New Witness?|
V---------------------------------V
/ \
(Yes) (No)
/ \
[Valid New Proof] [Extraction Fails /
Proof Rejected]
Achieving this property requires binding the proof uniquely to the specific context of the interaction. Andrew C Yao et al. address this in A New Family of Practical Non-Malleable Protocols by introducing a non-malleable joint proof-of-knowledge (NMJPOK). This mechanism forces a party to simultaneously prove knowledge of both long-term static secrets and temporary session exponents, preventing attackers from separating and reusing components of the proof in different contexts. This mirrors the foundational goals of concurrent zero-knowledge building blocks introduced by Boaz Barak et al. in How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.
Proving that a multi-round Fiat-Shamir protocol is simulation-extractable is notoriously difficult because the hash function links all rounds together. However, recent work has successfully closed this gap for widely deployed systems like Bulletproofs. Chaya Ganesh et al. provided the first formal proof of non-malleability for Bulletproofs within the Algebraic Group Model in Fiat–Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model). They subsequently eliminated the algebraic restriction in Fiat-Shamir Bulletproofs are Non-Malleable (in the Random Oracle Model) by combining standard proof extractability with a "weak unique response" property, proving that the Fiat-Shamir transform inherently resists malleability attacks when applied to well-structured multi-round protocols.
Key Foundational Work
Noninteractive Zero-Knowledge (1991) — contributed 3 concept elements to this direction.
Short Group Signatures (2004) — contributed 1 concept elements to this direction.