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 $s_1\text{,}\dots \text{,}{s}_k$. Let $v_i\equiv s_i^{-2}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ (we assume $gcd(s_i\text{,}n)=1$). The numbers $v_i$ are sent to Victor. Victor will try to verify that Peggy knows the numbers $s_1\text{,}\dots \text{,}{s}_k$. Peggy and Victor proceed as follows:

1. Peggy chooses a random integer $r$, computes $x\equiv r^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and sends $x$ to Victor.

2. Victor chooses numbers $b_1\text{,}\dots \text{,}{b}_k$ with each $b_i\in \{0\text{,}1\}$. He sends these to Peggy.

3. Peggy computes $y\equiv r{s}_1^{b_1}{s}_2^{b_2}\cdots s_k^{b_k}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and sends $y$ to Victor.

4. Victor checks that $x\equiv y^2{v}_1^{b_1}{v}_2^{b_2}\cdots v_k^{b_k}(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

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 $r{s}_1$. These are two random numbers whose quotient is a square root of $v_1$. 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 $b_1=1\text{,}{b}_2=1\text{,}{b}_4=1$, and all other $b_i=0$. Then Peggy must produce $y\equiv r{s}_1{s}_2{s}_4$, which is a square root of $x{v}_1^{-1}{v}_2^{-1}{v}_4^{-1}$. In fact, in each round, Victor is asking for a square root of a number of the form $x{v}_{i_1}^{-1}{v}_{i_2}^{-1}\cdots v_{i_j}^{-1}$. Peggy can supply a square root if she knows $r\text{,}{s}_{i_1}\text{,}\dots \text{,}{s}_{i_j}$. If she doesn’t, she will have a hard time computing a square root.

If Peggy doesn’t know any of the numbers $s_1\text{,}\dots \text{,}{s}_k$ (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 $x\equiv y^2{v}_1^{b_1}{v}_2^{b_2}\cdots v_k^{b_k}(\mathrm{m}\mathrm{o}\mathrm{d}n)$. 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 $v_i$’s.

For example, suppose Peggy is able to supply the correct response when $b_1=1\text{,}{b}_2=1\text{,}{b}_4=1$, and all other $b_i=0$. This could be accomplished by guessing the bits and using the preceding method of choosing $x$. However, suppose Victor sends $b_1=1\text{,}{b}_3=1$, and all other $b_i=0$. Then Peggy will be ready to supply a square root of $x{v}_1^{-1}{v}_2^{-1}{v}_4^{-1}$ but will be asked to supply a square root of $x{v}_1^{-1}{v}_3^{-1}$. This, combined with what she knows, is equivalent to knowing a square root of $v_2^{-1}{v}_3{v}_4^{-1}$, 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 $v_1{v}_2{v}_4$. In summary, if Peggy’s guess is not correct, she will need to know the square root of a nonempty product of $v_i$’s, which she cannot compute. Therefore, there are $2^k$ 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 $2^k$ that Victor will be fooled. If the procedure is repeated $t$ times, the chances are 1 in $2^{kt}$ 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, $s_1$, but he is very certain that Eve is not masquerading as Peggy, since Eve should not know any of the $s_i$’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 $y^2{v}_1^{b_1}{v}_2^{b_2}\cdots v_k^{b_k}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ 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(I\parallel j)$ for some small values of $j$, where $I\parallel j$ means $j$ is appended to $I$. Using his knowledge of $p\text{,}q$, he can determine which of these numbers $H(I\parallel j)$ have square roots mod $n$ and calculate a square root for each such number. This yields numbers $v_1=H(I\parallel j_1)\text{,}\dots \text{,}{v}_k=H(I\parallel j_k)$ and square roots $s_1\text{,}\dots \text{,}{s}_k$. The numbers $I\text{,}n\text{,}{j}_1\text{,}\dots \text{,}{j}_k$ are made public. Arthur gives the numbers $s_1\text{,}\dots \text{,}{s}_k$ to Peggy, who keeps them secret. The prime numbers $p\text{,}q$ are discarded once the square roots are calculated. Likewise, Arthur does not need to store $s_1\text{,}\dots \text{,}{s}_k$ 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(I\parallel j)$ has a 1/4 probability of having a square root mod $n$. This means that Arthur should be able to produce the necessary numbers $j_1\text{,}\dots \text{,}{j}_k$ quickly.

Peggy goes to an automatic teller machine, for example. The machine reads $I$ from Peggy’s card. It downloads $n\text{,}{j}_1\text{,}\dots \text{,}{j}_k$ from a database and calculates $v_i=H(I||j_i)$ for $1\le i\le k$. It then performs the preceding procedure to verify that Peggy knows $s_1\text{,}\dots \text{,}{s}_k$. 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 $s_1\text{,}\dots \text{,}{s}_k$ that can be reused in future transactions.