Chaincamp

A minimal blog on the building blocks of ethereum & cryptographic primitives

10 Mar 2024

Fiat–Shamir heuristic

Outline

  • The purpose and key concepts of the Fiat-Shamir heuristic, including interactive proof systems, zero-knowledge proofs, and random oracles
  • The mathematical setup and notation for the prover, verifier, and interactive protocol
  • Detailed computational steps to convert the interactive proof into a non-interactive proof using the Fiat-Shamir transformation
  • Prove the soundness and zero-knowledge properties of the resulting non-interactive proof system
  • Discuss applications, extensions, challenges and open problems related to the Fiat-Shamir heuristic
  • Reference seminal papers, textbooks and recent research, providing DOIs and brief descriptions of relevance
  • Explore thought-provoking questions on foundations, extensions and applications

Inputs

  • An interactive proof system $(P, V)$ for a language $L$, where:
    • $P$ is the prover, a probabilistic polynomial-time algorithm
    • $V$ is the verifier, a probabilistic polynomial-time algorithm
  • A cryptographic hash function $H$ modeled as a random oracle

The interactive proof system $(P, V)$ satisfies:

  • Completeness: If $x \in L$, then $\mathrm{Pr}[\langle P, V \rangle(x) = 1] \geq \frac{2}{3}$
  • Soundness: If $x \notin L$, then for any prover strategy $P^$, $\mathrm{Pr}[\langle P^, V \rangle(x) = 1] \leq \frac{1}{3}$

Computational Steps

The Fiat-Shamir heuristic transforms the interactive proof system $(P, V)$ into a non-interactive argument system $(\mathcal{P}, \mathcal{V})$ as follows:

  1. The prover $\mathcal{P}$ starts by running the interactive prover algorithm $P$ to generate its first message $a$.

  2. Instead of receiving a challenge from the verifier, $\mathcal{P}$ computes the challenge itself by applying the hash function $H$ to the concatenation of the input $x$ and the first message $a$:

    $e = H(x || a)$

    This step replaces the verifier’s random challenge in the interactive protocol.

  3. The prover $\mathcal{P}$ then runs the interactive prover algorithm $P$ to compute the response $z$ to the self-generated challenge $e$, as if $e$ was sent by the verifier.

  4. The final non-interactive proof consists of the tuple $\pi = (a, e, z)$.

  5. To verify the proof $\pi = (a, e, z)$, the verifier $\mathcal{V}$ checks that:

    $e \stackrel{?}{=} H(x || a)$

    $V(x, a, e, z) \stackrel{?}{=} 1$

    where $V$ is the verification algorithm of the original interactive proof system.

The key idea is that by generating the challenge with a hash function applied to the prover’s first message, the prover cannot anticipate the challenge in advance. The hash function therefore acts as an unbiased random oracle.

Under the random oracle model, the non-interactive argument system $(\mathcal{P}, \mathcal{V})$ satisfies:

  • Completeness: If $x \in L$, then $\mathrm{Pr}[\mathcal{V}(x, \mathcal{P}(x)) = 1] \geq \frac{2}{3}$
  • Soundness: If $x \notin L$, then for any prover strategy $\mathcal{P}^$, $\mathrm{Pr}[\mathcal{V}(x, \pi^) = 1] \leq \frac{1}{3} + \mathsf{negl}(n)$, where $\pi^* \leftarrow \mathcal{P}^*(x)$

The proof of soundness relies on the fact that if $x \notin L$, then for any fixed first message $a$, there is at most one challenge $e$ for which a valid response $z$ exists that makes the verifier accept. Since $e$ is generated as $e = H(x || a)$, the probability that $\mathcal{P}^*$ can generate $a$ such that $e$ is exactly the right challenge is negligible if $H$ is a random function.

The Fiat-Shamir heuristic preserves the zero-knowledge property of the original interactive proof system if it is honest-verifier zero-knowledge (HVZK). Intuitively, the simulated proof in the HVZK property can be generated without interacting with the prover by programming the random oracle, allowing the zero-knowledge simulator to work for the non-interactive argument.

Output

The non-interactive argument $\pi = (a, e, z)$, where:

  • $a$ is the prover’s first message
  • $e = H(x || a)$ is the challenge generated via the hash function
  • $z$ is the prover’s response to the self-generated challenge $e$

The verifier outputs 1 (accept) if $e = H(x || a)$ and $V(x, a, e, z) = 1$, else it outputs 0 (reject).

The Fiat-Shamir transformation can be applied to various interactive proof systems, including Schnorr’s identification protocol, the Guillou-Quisquater identification protocol, and the Chaum-Pedersen protocol, to obtain secure digital signature schemes. It is also used in the construction of many non-interactive zero-knowledge proof systems, such as zk-SNARKs.

Explore

  1. The Fiat-Shamir heuristic relies on modeling the hash function as a random oracle. However, can we instantiate the Fiat-Shamir transformation with a concrete hash function while retaining its security properties? This question leads to the area of research on the reducibility of the random oracle model.

  2. Can the Fiat-Shamir paradigm be extended to transform constant-round interactive proofs into non-interactive arguments? This would allow for the construction of more efficient non-interactive proof systems.

  3. The Fiat-Shamir heuristic is widely used in the construction of non-interactive zero-knowledge proofs, which have applications in blockchain protocols and privacy-preserving cryptography. However, the concrete efficiency and scalability of NIZK proofs based on Fiat-Shamir remain a challenge in practice. Can we optimize Fiat-Shamir based NIZKs for real-world deployment?

References

  • Fiat, A., & Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the Theory and Application of Cryptographic Techniques (pp. 186-194). Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12 (Original paper introducing the Fiat-Shamir heuristic)

  • Pointcheval, D., & Stern, J. (2000). Security arguments for digital signatures and blind signatures. Journal of cryptology, 13(3), 361-396. DOI: 10.1007/s001450010003 (Provides security proofs for Fiat-Shamir based signature schemes)

  • Lindell, Y. (2017). An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle. In Theory of Cryptography Conference (pp. 93-109). Springer, Cham. DOI: 10.1007/978-3-319-70500-2_4 (Discusses Fiat-Shamir in the context of constructing efficient NIZK proofs)