Feige–Fiat–Shamir identification scheme

The Fiat-Shamir protocol is a protocol from the area of ​​cryptography, which can be used to authenticate against someone. For this purpose, one can show that a square root (private key) knows a previously published square number (public key). In the method, only a single bit of the private key revealed, that the sign. A variation is to Feige - Fiat-Shamir protocol in which no information about the private key is retrieved. One therefore speaks of a zero-knowledge protocol. In particular, the protocol is perfect zero-knowledge. That is, there is a simulation algorithm that generates in polynomial time a transcript that is indistinguishable from a real interaction.

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

The process is interactive, that is, it will find several rounds of secret between carrier and the auditor instead. In each round, the knowledge of the number can be proved to be 50%. After two rounds remains an uncertainty of 25 %, after the third round, only 12.5 %, etc. After rounds of the uncertainty.

The security of the Fiat -Shamir protocol is based on the difficulty of calculating square roots in the residue class ring. This calculation is just as difficult as the number (and primes ) to factorize and therefore practically not feasible, if the numbers are sufficiently large.

Protocol

When Fiat -Shamir protocol, a trusted third party is needed. These published an RSA modulus whose prime factors and keeps it secret. The Beweiserin ( secret wearer ) Peggy chooses a prime number to a personal secret, with whom she wants to Victor ( V as verifier ) authenticate against. This they may not pass anyone. It calculates and records as a public key of the third party.

A single round in the Fiat -Shamir protocol consists of the following actions:

This protocol is not zero-knowledge as it reveals one bit of information about: Would Viktor learn in any way that applies to a number that he could safely decide whether or applies after execution of the protocol; he would have the missing bit so obtained information ( the sign of or ) from the data of the protocol.

In fig - Fiat -Shamir protocol Peggy sends in the first step either or Victor. The choice of the value it sends, she meets by chance. Viktor then checks in the last step that either or is true. Thus, the sign of is not revealed and the protocol is zero-knowledge.

Weaken

For the security of the protocol, the choice of the random number r is of great importance. If the same used twice and is once again 0 and 1, can be calculated, the private key.

Example

In both cases, has the same value.

  • Peggy transfers:
  • Peggy transfers:

An attacker can easily calculate now. This is no longer a secret, known only to Peggy.

Swell

  • Albrecht Beutelspacher, Jörg Panning, Klaus -Dieter Wolfstetter: 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 problem. In: Proceedings on Advances in Cryptology - CRYPTO '86. Springer - Verlag, 1987, ISBN 0-387-18047-8, pp. 186-194
  • Identification protocol
Time complexity#Polynomial time Alice and Bob
333264
de