Computer Security and Cryptography

17.12 THE FIAT–SHAMIR IDENTIFICATION AND SIGNATURE SCHEMA [FIAT AND SHAMIR, 1986]

User_ID[A] wants to prove identity to User_ID[B] by showing possession of some secret information without actually revealing this information. The Fiat–Shamir Identification Scheme was the first example of a zero-knowledge proof. Its strength and that of the following protocols depends on the computational equivalence of Problems A–C described in Section 17.6.

A trusted signature center chooses secret primes p, q and computes N = pq; only N is distributed to all users.

• User_ID[A] selects a random s, checks that 1 = gcd{s, N} and computes v⁻¹ = s² (modulo N).
• User_ID[A] registers ν with the trusted signature center.

s⁻¹ is a quadratic residue of ν. User_ID[A]'s will prove identity to User_ID[B] by exhibiting knowledge of the private key PrK(ID[A]) = s without actually revealing s.

S1. User_ID[A] chooses a random r in computes x = r² (modulo N) and sends x to User_ID[B].

S2. User_ID[B] chooses a random bit b = 0 or 1 (with probability 1/2) and sends it to User_ID[A].

S3. User_ID[A] returns y to User_ID[B] where

S4. User_ID[B] computes

and accepts the identification pass as valid if y²ν^b (modulo N) = ...