Fiat–Shamir heuristic

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

For the algorithm specified below, readers should be familiar with the laws of modular arithmetic, especially with multiplicative groups of integers modulo n with prime q.

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

  1. Peggy wants to prove to Victor the verifier that she knows : the discrete logarithm of to the base (mod n).
  2. She picks a random , computes and sends to Victor.
  3. Victor picks a random and sends it to Peggy.
  4. Peggy computes and returns to Victor.
  5. He checks whether . This holds because .

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 : the discrete logarithm of to the base .
  2. She picks a random and computes .
  3. Peggy computes , where is a cryptographic hash function.
  4. She computes . The resulting proof is the pair .
  5. Anyone can use this proof to calculate and check whether .

As is an exponent of and we're using cyclic groups with order , it can be calculated modulo , not modulo . is in the case when is prime order of group.

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 x so that the product cx is known.[8]

Extension of this method[edit]

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

References[edit]

  1. ^ Fiat, Amos; Shamir, Adi (1987). "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". Advances in Cryptology — CRYPTO' 86. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 263: 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". Advances in Cryptology — EUROCRYPT '96. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1070: 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". Advances in Cryptology — CRYPTO '19. Lecture Notes in Computer Science. Springer Cham. 11693: 356–383. arXiv:1902.07556. Bibcode:2019arXiv190207556D. doi:10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0.
  4. ^ Liu, Qipeng; Zhandry, Mark (2019). "Revisiting Post-quantum Fiat-Shamir". Advances in Cryptology — CRYPTO '19. Lecture Notes in Computer Science. Springer Cham. 11693: 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.: 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" (PDF). Dept. Of Computer Science, ETH Zurich.
  7. ^ Bellare, Mihir; Rogaway, Phillip (1995). "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols". ACM Press: 62–73. CiteSeerX 10.1.1.50.3345. Cite journal requires |journal= (help)
  8. ^ Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios" (PDF). In Wang, Xiaoyun; Sako, Kazue (eds.). Advances in Cryptology – ASIACRYPT 2012. pp. 626–643.