Fiat-Shamir heuristic

The Fiat-Shamir heuristic is a cryptographic technique that can be used to generate a digital signature from an interactive proof . In this way, a certain fact (e.g. knowledge of a certain number) can be proven without the underlying information becoming apparent. This technique was developed in 1986 by Amos Fiat and Adi Shamir . The original interactive evidence must have public-coin property for the method to take effect. For the algorithm given below, the reader should be familiar with modular arithmetic , especially those in the so-called P-groups .

The heuristic was originally presented without proof of security, later Pointcheval and Stern showed their security against the chosen plaintext attack in the random oracle model, that is, under the assumption that such random oracles exist. In the event that these do not exist, the Fiat-Shamir heuristic has been proven unsafe by Goldwasser and Kalai. If the hash value calculated below does not depend on the (public) value of , the security of the algorithm is compromised, as a malicious prover could set the value within a certain framework. ${\displaystyle y}$ ${\displaystyle c}$

In general, the Fiat-Shamir heuristic can be viewed as a way to convert an interactive public coin evidence into a non-interactive, zero-knowledge evidence. If the interactive evidence is an identification protocol, the non-interactive version can be used as a digital signature.

example

This is an interactive proof of knowing a discrete logarithm.

1. Alice wants to prove to Bob that she knows the discrete logarithm of the base . ${\displaystyle x}$ ${\displaystyle y=g^{x}}$ ${\displaystyle g}$
2. She dials in , calculates and sends to Bob. ${\displaystyle v\in \mathbb {Z} _{q}}$ ${\displaystyle t=g^{v}}$ ${\displaystyle t}$
3. Bob chooses a random one and sends it to Alice. ${\displaystyle c\in \mathbb {Z} _{q}^{*}}$
4. Alice calculates and sends to Bob. ${\displaystyle r=v-cx}$ ${\displaystyle r}$
5. Bob checks that (this statement is true there ). ${\displaystyle t\equiv g^{r}y^{c}}$ ${\displaystyle g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t}$

The Fiat-Shamir heuristic consists of replacing step 3 with a non-interactive access to a random oracle . In practice, a cryptographic hash function is used instead.

1. Alice wants to prove to Bob that she knows the discrete logarithm of the base . ${\displaystyle x}$ ${\displaystyle y=g^{x}}$ ${\displaystyle g}$
2. She dials in and calculates . ${\displaystyle v\in \mathbb {Z} _{q}}$ ${\displaystyle t=g^{v}}$
3. Alice calculates using a cryptographic hash function . ${\displaystyle c=H(g,y,t)}$ ${\displaystyle H()}$
4. You calculated . The proof is the couple . Since is an exponent of , is the modulus . ${\displaystyle r=v-cx}$ ${\displaystyle (t,r)}$ ${\displaystyle r}$ ${\displaystyle g}$ ${\displaystyle q-1}$
5. Anyone can check if . ${\displaystyle t\equiv g^{r}y^{c}}$

See also

• Random oracle
• Interactive evidence system

Individual evidence

1. ↑ Amos Fiat, Adi Shamir: How To Prove Yourself: Practical Solutions to Identification and Signature Problems . In: Andrew M. Odlyzko (Ed.): Advances in Cryptology - CRYPTO '86 (=  Lecture notes in computer science . Volume 263 ). Springer, Berlin / Heidelberg 1987, ISBN 3-540-18047-8 , pp. 186-194 .
2. ↑ David Pointcheval, Jacques Stern: Security Proofs for Signature Schemes . In: Ueli Maurer (Ed.): Advances in Cryptology - EUROCRYPT '96 . Springer, Berlin / Heidelberg 1996, ISBN 3-540-61186-X , p. 387-398 .
3. ^ S. Goldwasser, YT Kalai: On the (In) security of the Fiat-Shamir paradigm . In: Proceedings 44th Annual IEEE Symposium on Foundations of Computer Science, 2003 . 2003, p. 102-113 , doi : 10.1109 / SFCS.2003.1238185 .
4. ↑ David Bernhard, Olivier Pereira, Bogdan Warinschi: Advances in Cryptology - ASIACRYPT 2012 . Ed .: Xiaoyun Wang, Kazue Sako. How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios, p. 626-643 ( uclouvain.be [PDF]).
5. ↑ Jan Camenisch, Markus Stadler: Proof Systems for General Statements about Discrete Logarithms . In: Technical Report (Dept. of Computer Science, ETH Zurich) . No. 260, 1997.
6. ↑ Mihir Bellare, Phillip Rogaway: Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols . In: Proceedings of the 1st ACM Conference on Computer and Communications Security . ACM, New York, NY, USA 1993, ISBN 0-89791-629-8 , pp. 62-73 , doi : 10.1145 / 168588.168596 .