Fiat Shamir Protocol

The Fiat Shamir protocol is a protocol from the field of cryptography with which you can authenticate yourself to someone . To do this, one shows that one knows a square root ( private key ) of a previously published square number ( public key ). In the process, only a single bit of the private key is disclosed, namely the sign . One variant is the Feige-Fiat-Shamir protocol, in which no information about the private key is disclosed. This is why one speaks of a zero knowledge protocol . In particular, the protocol is perfectly zero-knowledge . This means that there is a simulation algorithm that generates a transcript in polynomial time that cannot be distinguished from a real interaction.

The Fiat-Shamir Protocol was introduced in 1986 by Amos Fiat and Adi Shamir . Uriel Feige was also involved in the development of the Feige-Fiat-Shamir Protocol .

The process works interactively, which means that several rounds take place between the person who kept the secret and the examiner. Knowledge of the number can be proven to 50% in each round. After two rounds there is an uncertainty of 25%, after the third round only 12.5%, etc. After rounds the uncertainty is equal to . ${\displaystyle n}$ ${\displaystyle 2^{-n}}$

The security of the Fiat-Shamir Protocol relies on the difficulty of computing square roots in the remainder class ring . This calculation is just as difficult as factoring the number ( and are prime numbers) and is therefore not practicable if the numbers are large enough. ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle n=p\cdot q}$ ${\displaystyle p}$ ${\displaystyle q}$

protocol

The Fiat Shamir Protocol requires a trusted third party . This publishes an RSA module whose prime factors and it keeps secret. The prover (holder of secrets) Peggy chooses a number that is too prime as a personal secret with which she wants to authenticate herself to Victor (V as in verifier). She is not allowed to pass this on to anyone. It is calculated and registered as a public key with the third party. ${\displaystyle n=p\cdot q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle v\equiv s^{2}{\bmod {n}}}$ ${\displaystyle v}$

A single lap in the Fiat Shamir Protocol consists of the following actions:

1. Peggy picks a random number , calculates it and sends it to Victor. ${\displaystyle r}$ ${\displaystyle x\equiv r^{2}{\bmod {n}}}$ ${\displaystyle x}$
2. Victor dials in randomly and sends it to Peggy. ${\displaystyle e\in \{0,1\}}$
3. Peggy calculates and sends to Victor. ${\displaystyle y\equiv r\cdot s^{e}{\bmod {n}}}$ ${\displaystyle y}$
4. Victor checks whether applies. ${\displaystyle y^{2}\equiv x\cdot v^{e}{\pmod {n}}}$

This protocol is not yet zero-knowledge, as it reveals one bit of information about : If Viktor learned in some way that a number applies, he could safely decide after execution of the protocol whether or applies; he would have obtained the missing bit of information (the sign of or ) from the data of the protocol. ${\displaystyle r\,{\bmod {n}}}$ ${\displaystyle r\equiv \pm \,c\,{\bmod {n}}}$ ${\displaystyle c}$ ${\displaystyle r\equiv c\,{\bmod {n}}}$ ${\displaystyle r\equiv -c\,{\bmod {n}}}$ ${\displaystyle c}$ ${\displaystyle r}$

In the Feige-Fiat-Shamir protocol, Peggy sends either or to Victor in the first step . The choice of which value it sends is made randomly. Viktor then checks in the last step that either or applies. As a result, the sign of is not disclosed and the protocol is zero-knowledge. ${\displaystyle x}$ ${\displaystyle -x\,{\bmod {n}}}$ ${\displaystyle y^{2}\equiv x\cdot v^{e}{\bmod {n}}}$ ${\displaystyle y^{2}\equiv -x\cdot v^{e}{\bmod {n}}}$ ${\displaystyle c}$

weaknesses

The choice of the random number r is of great importance for the security of the protocol.
If the same is used twice and is 0 once and 1 once, the private key can be calculated. ${\displaystyle r}$ ${\displaystyle e}$

example

Has the same value in both cases . ${\displaystyle x\equiv r^{2}{\bmod {n}}}$

1. round
   • ${\displaystyle e_{1}=0}$
   • Peggy transmits: ${\displaystyle y_{1}\equiv r\,{\bmod {n}}}$
2. round
   • ${\displaystyle e_{2}=1}$
   • Peggy transmits: ${\displaystyle y_{2}\equiv r\cdot s{\bmod {n}}}$

An attacker can now simply calculate. This is no longer a secret that only Peggy knows. ${\displaystyle s}$ ${\displaystyle s}$
${\displaystyle s\equiv y_{2}\cdot r^{-1}\equiv y_{2}\cdot y_{1}^{-1}{\bmod {n}}}$

swell

• Albrecht Beutelspacher , Jörg Schwenk, Klaus-Dieter Wolfenstetter: Modern methods of cryptography. Vieweg + Teubner, Braunschweig / Wiesbaden 2010, 7th edition, ISBN 978-3-8348-1228-5 , pp. 49-50
• Amos Fiat , Adi Shamir : How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Proceedings on Advances in Cryptology - CRYPTO '86. Springer-Verlag, 1987, ISBN 0-387-18047-8 , pp. 186-194