# 19.2 The Feige-Fiat-Shamir Identification Scheme

The preceding protocol requires several communications between Peggy and Victor. The Feige-Fiat-Shamir method reduces this number and uses a type of parallel verification. This then is used as the basis of an identification scheme.

Again, let  be the product of two large primes. Peggy has secret numbers . Let  (we assume ). The numbers  are sent to Victor. Victor will try to verify that Peggy knows the numbers . Peggy and Victor proceed as follows:

1. Peggy chooses a random integer , computes  and sends  to Victor.

2. Victor chooses numbers  with each . He sends these to Peggy.

3. Peggy computes  and sends  to Victor.

4. Victor checks that .

5. Steps 1 through 4 are repeated several times (each time with a different ).

Consider the case . Then Peggy is asked for either  or . These are two random numbers whose quotient is a square root of . Therefore, this is essentially the same idea as the simplified scheme discussed previously, with quotients instead of products.

Now let’s analyze the case of larger . Suppose, for example, that Victor sends , and all other . Then Peggy must produce , which is a square root of . In fact, in each round, Victor is asking for a square root of a number of the form . Peggy can supply a square root if she knows . If she doesn’t, she will have a hard time computing a square root.

If Peggy doesn’t know any of the numbers  (the likely scenario also if someone other than Peggy is pretending to be Peggy), she could guess the string of bits that Victor will send. Suppose she guesses correctly, before she sends . She lets  be a random number and declares . When Victor sends the string of bits, Peggy sends back the value of . Of course, the verification congruence is satisfied. But if Peggy guesses incorrectly, she will need to modify her choice of , which means she will need some square roots of ’s.

For example, suppose Peggy is able to supply the correct response when , and all other . This could be accomplished by guessing the bits and using the preceding method of choosing . However, suppose Victor sends , and all other . Then Peggy will be ready to supply a square root of  but will be asked to supply a square root of . This, combined with what she knows, is equivalent to knowing a square root of , which she is not able to compute. In an extreme case, Victor could send all bits equal to 0, which means Peggy must supply a square root of . With Peggy’s guess as before, this means she would know a square root of . In summary, if Peggy’s guess is not correct, she will need to know the square root of a nonempty product of ’s, which she cannot compute. Therefore, there are  possible strings of bits that Victor can send, and only one will allow Peggy to fool Victor. In one iteration of the protocol, the chances are only one in  that Victor will be fooled. If the procedure is repeated  times, the chances are 1 in  that Victor is fooled. Recommended values are  and . Note that this gives the same probability as 20 iterations of the earlier scheme, so the present procedure is more efficient in terms of communication between Peggy and Victor. Of course, Victor has not obtained as strong a verification that Peggy knows, for example, , but he is very certain that Eve is not masquerading as Peggy, since Eve should not know any of the ’s.

There is an interesting feature of how the numbers are arranged in Steps 1 and 4. It is possible for Peggy to use a cryptographic hash function and send the hash of  after computing it in Step 1. After Victor computes  in Step 4, he can compute the hash of this number and compare with the hash sent by Peggy. The hash function is assumed to be collision resistant, so Victor can be confident that the the congruence in Step 4 is satisfied. Since the output of the hash function is probably shorter than  (for example, 256 bits for the hash, compared to 2048 bits for ), this saves a few bits of transmission.

The preceding can be used to design an identification scheme. Let  be a string that includes Peggy’s name, birth date, and any other information deemed appropriate. Let  be a public hash function. A trusted authority Arthur (the bank, a passport agency, ...) chooses  to be the product of two large primes. Arthur computes  for some small values of , where  means  is appended to . Using his knowledge of , he can determine which of these numbers  have square roots mod  and calculate a square root for each such number. This yields numbers  and square roots . The numbers  are made public. Arthur gives the numbers  to Peggy, who keeps them secret. The prime numbers  are discarded once the square roots are calculated. Likewise, Arthur does not need to store  once they are given to Peggy. These two facts add to the security, since someone who breaks into Arthur’s computer cannot compromise Peggy’s security. Moreover, a different  can be used for each person, so it is hard to compromise the security of more than one individual at a time.

Note that since approximately half the numbers mod  and half the numbers mod  have square roots, the Chinese remainder theorem implies that approximately 1/4 of the numbers mod  have square roots. Therefore, each  has a 1/4 probability of having a square root mod . This means that Arthur should be able to produce the necessary numbers  quickly.

Peggy goes to an automatic teller machine, for example. The machine reads  from Peggy’s card. It downloads  from a database and calculates  for . It then performs the preceding procedure to verify that Peggy knows . After a few iterations, the machine is convinced that the person is Peggy and allows her to withdraw cash. A naive implementation would require a lot of typing on Peggy’s part, but at least Eve won’t get Peggy’s secret numbers. A better implementation would use chips embedded in the card and store some information in such a way that it cannot be extracted.

If Eve obtains the communications used in the transaction, she cannot determine Peggy’s secret numbers. In fact, because of the zero-knowledge nature of the protocol, Eve obtains no information on the secret numbers  that can be reused in future transactions.