Feige-Fiat-Shamir Identification Scheme

From Wikipedia, the free encyclopedia

In cryptography, the Feige-Fiat-Shamir Identification Scheme is a type of parallel zero-knowledge proof developed by Uriel Feige, Amos Fiat, and Adi Shamir in 1988. Like all zero-knowledge proofs, the Feige-Fiat-Shamir Identification Scheme allows one party, Alice, to prove to another party, Bob, that she possesses secret information without revealing to Bob what that secret information is. The Feige-Fiat-Shamir Identification Scheme, however, uses modular arithmetic and a parallel verification process that limits the number of communications between Alice and Bob.

1 Setup
2 Procedure
3 Security
4 References

[edit] Setup

Choose two large prime integers p and q and compute the product n = pq. Create secret numbers $s_1, \cdots, s_k$ with gcd( $s i$ , $n$ ) = 1. Compute $v_i \equiv s_i^{2} \pmod{n}$ . Alice and Bob both receive $n$ while $p$ and $q$ are kept secret. Alice is then sent the numbers $s i$ . These are her secret login numbers. Bob is sent the numbers $v i$ . Bob is unable to recover Alice's $s i$ numbers from his $v i$ numbers due to the difficulty in determining a modular square root when the modulus' factorization is unknown.

[edit] Procedure

Alice chooses a random integer $r$ , a random sign $s\in\{-1,1\}$ and computes $x \equiv s\cdot r^2 \pmod{n}$ . Alice sends this number to Bob.
Bob chooses numbers $a_1, \cdots, a_k$ where $a i$ equals 0 or 1. Bob sends these numbers to Alice.
Alice computes $y \equiv rs_1^{a_1}s_2^{a_2} \cdots s_k^{a_k}\pmod{n}$ . Alice sends this number to Bob.
Bob checks that $y^2 \equiv \pm\, x v_1^{a_1}v_2^{a_2} \cdots v_k^{a_k}\pmod{n}$ .

This procedure is repeated with different $r$ and $a i$ values until Bob is satisfied that Alice does indeed possess the modular square roots ( $s i$ ) of his $v i$ numbers.

[edit] Security

In the procedure, Alice does not give any useful information to Bob. She merely proves to Bob that she has the secret numbers without revealing what those numbers are. Anyone who intercepts the communication between each Alice and Bob would only learn the same information. The eavesdropper would not learn anything useful about Alice's secret numbers.

In an early version, the Fiat-Shamir-Scheme (on which the Feige-Fiat-Shamir-Scheme was based), one bit of information was leaked. By the introduction of the sign $s$ even this bit was concealed resulting in a zero-knowledge-protocol.

Suppose Eve has intercepted Bob's $v i$ numbers but does not know what Alice's $s i$ numbers are. If Eve wants to try to convince Bob that she is Alice, she would have to correctly guess what Bob's $a i$ numbers will be. She then picks a random $y$ , calculates $x \equiv y^2 v_1^{-a_1}v_2^{-a_2} \cdots v_k^{-a_k}\pmod{n}$ and sends $x$ to Bob. When Bob sends $a i$ , Eve simply returns her $y$ . Bob is satisfied and concludes that Eve has the secret numbers. However, the probablity of Eve correctly guessing what Bob's $a i$ will be is 1 in $2 k$ . By repeating the procedure $t$ times, the probability drops to 1 in $2 k t$ . For $k = 5$ and $t = 4$ the probability of successfully posing as Alice is less than 1 in 1 million.