Fiat–Shamir heuristic

The Fiat–Shamir heuristic is a technique in cryptography for taking an interactive proof of knowledge and creating a digital signature based on it. The technique is due to Fiat and Shamir (1986).[1] The original interactive proof must have the property of being public-coin, for the method to work.

The heuristic was originally presented without a proof of security; later, Pointcheval and Stern [2] proved its security against chosen message attacks in the random oracle model, that is, under the assumption that random oracles exist. In the case that random oracles don't exist, the Fiat–Shamir heuristic has been proven insecure by Goldwasser and Kalai.[3] The Fiat–Shamir heuristic thus demonstrates a major application of random oracles.

More generally, the Fiat–Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into a non-interactive proof of knowledge. If the interactive proof is an identification protocol, then the non-interactive version can be used directly as a digital signature.

Example

Here is an interactive proof of knowledge of a discrete logarithm.[4]

  1. Alice want to prove to Bob that she knows x: discrete logarithm of y = gx to the base g.
  2. She picks a random v∈ℤq, computes t = gv and sends t to Bob.
  3. Bob picks a random c∈ℤ*q and sends it to Alice.
  4. Alice computes r = v - cx and returns r to Bob.
  5. He checks if t ≡ gryc (it holds, because gryc = gv - cxgxc = gv = t).

Fiat-Shamir heuristic allows to replace the interactive step 3 with a non-interactive random oracle access. In practice, we can use a cryptographic hash function instead.[5]

  1. Alice want to prove that she knows x: discrete logarithm of y = gx to the base g.
  2. She picks a random v∈ℤq and computes t = gv.
  3. Alice computes c = H(g,y,t), where H() is a cryptographic hash function.
  4. She computes r = v - cx. The resulting proof is the pair (t,r).
  5. Anyone can check if t ≡ gryH(g,y,t).

See also

References

  1. ↑ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
  2. ↑ David Pointcheval and Jacques Stern: Security Proofs for Signature Schemes. EUROCRYPT 1996: pp. 387-398
  3. ↑ Shafi Goldwasser and Yael Kalai: On the (In)security of the Fiat-Shamir Paradigm. FOCS 2003: pp. 102
  4. ↑ Camenisch, Jan; Stadler, Markus (1997). "Proof Systems for General Statements about Discrete Logarithms". Dept. of Computer Science, ETH Zurich.
  5. ↑ Bellare, Mihir; Rogaway, Phillip (1993). "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols". ACM.