19.2 The Feige-Fiat-Shamir Identification Scheme – Introduction to Cryptography with Coding Theory, 3rd Edition

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 n=pq be the product of two large primes. Peggy has secret numbers s1, , sk. Let visi2  (modn) (we assume gcd(si, n)=1). The numbers vi are sent to Victor. Victor will try to verify that Peggy knows the numbers s1, , sk. Peggy and Victor proceed as follows:

  1. Peggy chooses a random integer r, computes xr2  (modn) and sends x to Victor.

  2. Victor chooses numbers b1, , bk with each bi{0, 1}. He sends these to Peggy.

  3. Peggy computes yrs1b1s2b2skbk  (modn) and sends y to Victor.

  4. Victor checks that xy2v1b1v2b2vkbk  (modn).

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

Consider the case k=1. Then Peggy is asked for either r or rs1. These are two random numbers whose quotient is a square root of v1. 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 k. Suppose, for example, that Victor sends b1=1, b2=1, b4=1, and all other bi=0. Then Peggy must produce yrs1s2s4, which is a square root of xv11v21v41. In fact, in each round, Victor is asking for a square root of a number of the form xvi11vi21vij1. Peggy can supply a square root if she knows r, si1, , sij. If she doesn’t, she will have a hard time computing a square root.

If Peggy doesn’t know any of the numbers s1, , sk (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 x. She lets y be a random number and declares xy2v1b1v2b2vkbk  (modn). When Victor sends the string of bits, Peggy sends back the value of y. Of course, the verification congruence is satisfied. But if Peggy guesses incorrectly, she will need to modify her choice of y, which means she will need some square roots of vi’s.

For example, suppose Peggy is able to supply the correct response when b1=1, b2=1, b4=1, and all other bi=0. This could be accomplished by guessing the bits and using the preceding method of choosing x. However, suppose Victor sends b1=1, b3=1, and all other bi=0. Then Peggy will be ready to supply a square root of xv11v21v41 but will be asked to supply a square root of xv11v31. This, combined with what she knows, is equivalent to knowing a square root of v21v3v41, 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 x. With Peggy’s guess as before, this means she would know a square root of v1v2v4. In summary, if Peggy’s guess is not correct, she will need to know the square root of a nonempty product of vi’s, which she cannot compute. Therefore, there are 2k 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 2k that Victor will be fooled. If the procedure is repeated t times, the chances are 1 in 2kt that Victor is fooled. Recommended values are k=5 and t=4. 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, s1, but he is very certain that Eve is not masquerading as Peggy, since Eve should not know any of the si’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 x after computing it in Step 1. After Victor computes y2v1b1v2b2vkbk  (modn) 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 x (for example, 256 bits for the hash, compared to 2048 bits for x), this saves a few bits of transmission.

The preceding can be used to design an identification scheme. Let I be a string that includes Peggy’s name, birth date, and any other information deemed appropriate. Let H be a public hash function. A trusted authority Arthur (the bank, a passport agency, ...) chooses n=pq to be the product of two large primes. Arthur computes H(Ij) for some small values of j, where Ij means j is appended to I. Using his knowledge of p, q, he can determine which of these numbers H(Ij) have square roots mod n and calculate a square root for each such number. This yields numbers v1=H(Ij1), , vk=H(Ijk) and square roots s1, , sk. The numbers I, n, j1, , jk are made public. Arthur gives the numbers s1, , sk to Peggy, who keeps them secret. The prime numbers p, q are discarded once the square roots are calculated. Likewise, Arthur does not need to store s1, , sk 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 n 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 p and half the numbers mod q have square roots, the Chinese remainder theorem implies that approximately 1/4 of the numbers mod n have square roots. Therefore, each H(Ij) has a 1/4 probability of having a square root mod n. This means that Arthur should be able to produce the necessary numbers j1, , jk quickly.

Peggy goes to an automatic teller machine, for example. The machine reads I from Peggy’s card. It downloads n, j1, , jk from a database and calculates vi=H(I||ji) for 1ik. It then performs the preceding procedure to verify that Peggy knows s1, , sk. 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 s1, , sk that can be reused in future transactions.