Fiat–Shamir heuristic

From HandWiki

In cryptography, the Fiat–Shamir heuristic is a technique for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact (for example, knowledge of a certain secret number) can be publicly proven without revealing underlying information. The technique is due to Amos Fiat and Adi Shamir (1986).[1] For the method to work, the original interactive proof must have the property of being public-coin, i.e. verifier's random coins are made public throughout the proof protocol.

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, assuming random oracles exist. This result was generalized to the quantum-accessible random oracle (QROM) by Don, Fehr, Majenz and Schaffner,[3] and concurrently by Liu and Zhandry.[4] In the case that random oracles do not exist, the Fiat–Shamir heuristic has been proven insecure by Shafi Goldwasser and Yael Tauman Kalai.[5] 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 used as an identification tool, then the non-interactive version can be used directly as a digital signature by using the message as part of the input to the random oracle.

Example

For the algorithm specified below, readers should be familiar with the multiplicative groups [math]\displaystyle{ \Z^* q }[/math], where q is a prime number, and Euler's totient theorem on the Euler's totient function φ.

Here is an interactive proof of knowledge of a discrete logarithm in [math]\displaystyle{ \Z^* q }[/math], based on Schnorr signature.[6] The public values are [math]\displaystyle{ y \in \Z^* q }[/math] and a generator g of [math]\displaystyle{ \Z^* q }[/math], while the secret value is the discrete logarithm of y to the base g.

  1. Peggy wants to prove to Victor, the verifier, that she knows [math]\displaystyle{ x }[/math] satisfying [math]\displaystyle{ y \equiv g^x }[/math] without revealing [math]\displaystyle{ x }[/math].
  2. She picks a random [math]\displaystyle{ v\in \Z^*_q }[/math], computes [math]\displaystyle{ t = g^v }[/math] and sends [math]\displaystyle{ t }[/math] to Victor.
  3. Victor picks a random [math]\displaystyle{ c\in \Z^*_q }[/math] and sends it to Peggy.
  4. Peggy computes [math]\displaystyle{ r = v - cx \bmod \varphi(q) }[/math] and returns [math]\displaystyle{ r }[/math] to Victor.
  5. He checks whether [math]\displaystyle{ t \equiv g^ry^c }[/math]. This holds because [math]\displaystyle{ g^ry^c \equiv g^{v - cx}g^{xc} \equiv g^v \equiv t }[/math] and [math]\displaystyle{ g^{\varphi(q)} \equiv 1 }[/math].

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.[7]

  1. Peggy wants to prove that she knows [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ y \equiv g^x }[/math] without revealing [math]\displaystyle{ x }[/math].
  2. She picks a random [math]\displaystyle{ v\in\Z^*_q }[/math] and computes [math]\displaystyle{ t = g^v }[/math].
  3. Peggy computes [math]\displaystyle{ c = H(g,y,t) }[/math], where [math]\displaystyle{ H }[/math] is a cryptographic hash function.
  4. She computes [math]\displaystyle{ r = v - cx \bmod \varphi(q) }[/math]. The resulting proof is the pair [math]\displaystyle{ (t,r) }[/math].
  5. Anyone can use this proof to calculate [math]\displaystyle{ c }[/math] and check whether [math]\displaystyle{ t \equiv g^ry^c }[/math].

If the hash value used below does not depend on the (public) value of y, the security of the scheme is weakened, as a malicious prover can then select a certain value t so that the product cx is known.[8]

Extension of this method

As long as a fixed random generator can be constructed with the data known to both parties, then any interactive protocol can be transformed into a non-interactive one.[citation needed]

See also

References

  1. ↑ Fiat, Amos; Shamir, Adi (1987). "How to Prove Yourself: Practical Solutions to Identification and Signature Problems" (in en). Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. 263. Springer Berlin Heidelberg. pp. 186–194. doi:10.1007/3-540-47721-7_12. ISBN 978-3-540-18047-0. 
  2. ↑ Pointcheval, David; Stern, Jacques (1996). "Security Proofs for Signature Schemes" (in en). Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. 1070. Springer Berlin Heidelberg. pp. 387–398. doi:10.1007/3-540-68339-9_33. ISBN 978-3-540-61186-8. 
  3. ↑ Don, Jelle; Fehr, Serge; Majenz, Christian; Schaffner, Christian (2019). "Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model" (in en). Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. 11693. Springer Cham. pp. 356–383. doi:10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0. Bibcode: 2019arXiv190207556D. 
  4. ↑ Liu, Qipeng; Zhandry, Mark (2019). "Revisiting Post-quantum Fiat-Shamir" (in en). Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. 11693. Springer Cham. pp. 326–355. doi:10.1007/978-3-030-26951-7_12. ISBN 978-3-030-26950-0. 
  5. ↑ Goldwasser, S.; Kalai, Y. T. (October 2003). "On the (In)security of the Fiat-Shamir paradigm". 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. pp. 102–113. doi:10.1109/SFCS.2003.1238185. ISBN 0-7695-2040-5. 
  6. ↑ Camenisch, Jan; Stadler, Markus (1997). "Proof Systems for General Statements about Discrete Logarithms". Dept. Of Computer Science, ETH Zurich. ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf. 
  7. ↑ Bellare, Mihir; Rogaway, Phillip (1995). Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. ACM Press. pp. 62–73. 
  8. ↑ Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios". Advances in Cryptology – ASIACRYPT 2012. pp. 626–643. http://www.uclouvain.be/crypto/services/download/publications.pdf.87e67d05ee05000b.6d61696e2e706466.pdf. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Fiat–Shamir_heuristic&oldid=3359145"