|Previous||Table of Contents||Next|
Amos Fiats and Adi Shamirs 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 . 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 werent 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 .
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 Peggys 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 x2 ≡ v (mod n) has a solution and v-1 mod n exists. This v is Peggys public key. Then calculate the smallest s for which s ≡ sqrt (v-1) (mod n). This is Peggys private key.
The identification protocol can now proceed.
This is a single roundcalled an accreditationof the protocol. Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy knows s. Its a cut-and-choose protocol. If Peggy doesnt 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 cant do both. The odds of her fooling Victor once are 50 percent. The odds of her fooling him t times are 1 in 2t.
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 2t.
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 Peggys responses. Then, from even one of these, he can calculate s and its 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 Victors interactions.
First generate n as in the previous example, the product of two large primes. To generate Peggys public and private keys, first choose k different numbers: v1, v2,..., vk, where each vi is a quadratic residue mod n. In other words, choose vi such that x2 = vi mod n has a solution and vi-1 mod n exists. This string, v1, v2,..., vk, is the public key. Then calculate the smallest si such that si = sqrt (vi-1) mod n. This string, s1, s2,..., sk, is the private key.
And the protocol is:
Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy knows s1, s2,..., sk.
The chance that Peggy can fool Victor is 1 in 2kt. 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.
|Previous||Table of Contents||Next|