Chapter 21
Identification Schemes

21.1 Feige-Fiat-Shamir

Amos Fiat’s and Adi Shamir’s authentication and digital signature scheme is discussed in [566,567]. Uriel Feige, Fiat, and Shamir modified the algorithm to a zero-knowledge proof of identity [544,545]. This is the best-known zero-knowledge proof of identity.

On July 9, 1986 the three authors submitted a U.S. patent application [1427]. Because of its potential military applications, the application was reviewed by the military. Occasionally the Patent Office responds not with a patent, but with something called a secrecy order. On January 6, 1987, three days before the end of their six-month period, the Patent Office imposed that order at the request of the Army. They stated that “...the disclosure or publication of the subject matter...would be detrimental to the national security....” The authors were ordered to notify all Americans to whom the research had been disclosed that unauthorized disclosure could lead to two years’ imprisonment, a $10,000 fine, or both. Furthermore, the authors had to inform the Commissioner of Patents and Trademarks of all foreign citizens to whom the information had been disclosed.

This was ludicrous. All through the second half of 1986, the authors had presented the work at conferences throughout Israel, Europe, and the United States. The authors weren’t even American citizens, and all the work had been done at the Weizmann Institute in Israel.

Word spread through the academic community and the press. Within two days the secrecy order was rescinded; Shamir and others believe that the NSA pulled strings to rescind the order, although they officially had no comment. Further details of this bizarre story are in [936].

Simplified Feige-Fiat-Shamir Identification Scheme

Before issuing any private keys, the arbitrator chooses a random modulus, n, which is the product of two large primes. In real life, n should be at least 512 bits long and probably closer to 1024 bits. This n can be shared among a group of provers. (Choosing a Blum integer makes computation easier, but it is not required for security.)

To generate Peggy’s public and private keys, a trusted arbitrator chooses a number, v, where v is a quadratic residue mod n. In other words, choose v such that x² ≡ v (mod n) has a solution and v^-1 mod n exists. This v is Peggy’s public key. Then calculate the smallest s for which s ≡ sqrt (v^-1) (mod n). This is Peggy’s private key.

The identification protocol can now proceed.

(1)  Peggy picks a random r, where r is less then n. She then computes x = r² mod n, and sends x to Victor.

(2)  Victor sends Peggy a random bit, b.

(3)  If b = 0, then Peggy sends Victor r. If b = 1, then Peggy sends Victor y = r * s mod n.

(4)  If b = 0, Victor verifies that x = r² mod n, proving that Peggy knows sqrt (x). If b = 1, Victor verifies that x = y² * v mod n, proving that Peggy knows sqrt (v^-1).

This is a single round—called an accreditation—of the protocol. Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy knows s. It’s a cut-and-choose protocol. If Peggy doesn’t know s, she can pick r such that she can fool Victor if he sends her a 0, or she can pick r such that she can fool Victor if he sends her a 1. She can’t do both. The odds of her fooling Victor once are 50 percent. The odds of her fooling him t times are 1 in 2^t.

Another way for Victor to attack the protocol would be trying to impersonate Peggy. He could initiate the protocol with another verifier, Valerie. In step (1), instead of choosing a random r, he would just reuse an old r that he saw Peggy use. However, the odds of Valerie choosing the same value for b in step (2) that Victor did in the protocol with Peggy are 1 in 2. So, the odds of his fooling Valerie are 50 percent. The odds of his fooling her t times are 1 in 2^t.

For this to work, Peggy must not reuse an r, ever. If she did, and Victor sent Peggy the other random bit in step (2), then he would have both of Peggy’s responses. Then, from even one of these, he can calculate s and it’s all over for Peggy.

Feige-Fiat-Shamir Identification Scheme

In their papers [544,545], Feige, Fiat and Shamir show how parallel construction can increase the number of accreditations per round and reduce Peggy and Victor’s interactions.

First generate n as in the previous example, the product of two large primes. To generate Peggy’s public and private keys, first choose k different numbers: v_1, v_2,..., v_k, where each v_i is a quadratic residue mod n. In other words, choose v_i such that x² = v_i mod n has a solution and v_i^-1 mod n exists. This string, v_1, v_2,..., v_k, is the public key. Then calculate the smallest s_i such that s_i = sqrt (v_i^-1) mod n. This string, s_1, s_2,..., s_k, is the private key.

And the protocol is:

(1)  Peggy picks a random r, when r is less than n. She then computes x = r² mod n, and sends x to Victor.

(2)  Victor sends Peggy a random binary string k-bits long: b_1, b_2,..., b_k.

(3)  Peggy computes y = r * (s₁^b1 * s₂^b2 *...* s_k^bk) mod n. (She multiplies together whichever values of s_i that correspond to bi = 1. If Victor’s first bit is a 1, then s₁ is part of the product; if Victor’s first bit is a 0, then s₁ is not part of the product, and so on.) She sends y to Victor.

(4)  Victor verifies that x = y² * (v₁^b1 * v₂^b2 *...* v_k^bk) mod n. (He multiplies together the values of v_i based on the random binary string. If his first bit is a 1, then v₁ is part of the product; if his first bit is a 0, then v₁ is not part of the product, and so on.)

Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy knows s_1, s_2,..., s_k.

The chance that Peggy can fool Victor is 1 in 2^kt. The authors recommend a 1 in 220 chance of a cheater fooling Victor and suggest that k = 5 and t = 4. If you are more paranoid, increase these numbers.