Zero-Knowledge Techniques and the Fiege-Fiat-Shamir Identification Scheme

Imagine that you've been selected to be a member of a secret society. You're given the password to enter the clubhouse, and thus have all the information you need to prove your membership. However, unbeknownst to you, there's an eavesdropper at the door who overhears you whisper your password to the guard. The society's meetings are now compromised, because a third party is mistakenly allowed entry.In the digital world, this is a serious problem, and there are many instances in which it's very important to be able to establish the identity of a user without revealing confidential information in the process, such as in online banking transactions. In these cases, a zero-knowledge proof - wherein one proves they possess some knowledge without revealing their knowledge - is employed. By convention, we identify three characters in the exchange: Peggy, the prover; Victor, the verifier; and Eve, the eavesdropper who may observe Peggy and Victor's interactions.To provide an example, consider the classic scenario described by Quisquater, Guillou, and Berson. Peggy and Victor are outside of a ring-shaped passageway, as pictured below. There are two ways in and out of the passage, marked A and B. Between A and B, there is a locked door. Peggy wants to demonstrate to Victor that she is able to unlock the door, but doesn't want Victor to know how she does it.First, Peggy goes down into the passageway, choosing to take A or B at random. Then, Victor waits at the intersection (marked X) and calls out "A" or "B," and Peggy emerges from the specified path. Note: that with probability p = 1/2, Peggy will not need to go through the door at all; she will have happened to select the same path that Victor chooses. Thus, the procedure is repeated many times, until Victor is satisfied that Peggy can in fact open the door. Definition of a Zero-Knowledge ProofThere are three properties required for a protocol to be considered a zero-knowledge proof: completeness, soundness and the zero-knowledge property.As we've seen, a zero-knowledge "proof" is not a proof in any formal mathematical sense, but rather a verification with some probability that approaches certainty.Completeness: The prover must be able to demonstrate to the verifier that she possesses the information. In this case, Peggy does this by exiting the passage via a certain pathway.Soundness: The prover should not be able to convince the verifier without actually possessing the information. In the previous example, the chance of Peggy emerging from the correct tunnel n times without being able to unlock the door is p = 1/2n, which becomes less than 1% with more than six iterations. This probability is known as the soundness error.Zero-knowledge: The verifier should not be able to determine the information by the prover's proof. Additionally, a third party observing the prover and the verifier should, at no point, be able to determine the information. This is analogous to saying that Victor, despite accepting that Peggy knows how to go through the door, cannot do so himself, nor could Eve if she viewed the entire exchange.Many different zero-knowledge proofs have been invented, most of them employing a one-way function as their primary mechanism for maintaining security. A one-way function is a relation that is very easy to computer in one direction, and computationally, very difficult in the other direction. Two examples of such functions, both of which have been used in zero-knowledge proofs, are taking a discrete logarithm and finding the Hamiltonian cycle of a graph. Fiege-Fiat-Shamir IdentificationOne of the most popular applications of a zero-knowledge proof is the protocol developed by Uriel Fiege, Amos Fiat, and Adi Shamir in 1988. The protocol allows for Peggy to prove to Victor that she possesses secret numbers s1...sk, which must be co-prime to n (sharing no common factors besides 1), without revealing anything about the numbers. It takes advantage of the difficulty of calculating modular square roots. The way it works is as follows:

1. First, Peggy and Victor choose n such that n is the product of two large primes, p and q, so n = pq. Additionally, Victor is sent v1...vk, where vi ≡ si2 mod n for all i, before the verification process begins.
2. Peggy chooses a random integer r and random sign α. She computes x ≡ α × r2 mod n, and sends x to Victor.
3. Victor chooses a random sequence of k bits b1...bk, and sends b1...bk to Peggy.
4. Peggy computes y = r × s1b1 s2b2 ...skbk mod n, the product mod n of each s corresponding to an “on” bit, and sends y back to Victor.
5. Finally, Victor compares y2 to x × v1b1 v2b2 ...vkbk mod n. If y2 ≡ x × v1b1 v2b2 ...vkbk mod n, Peggy likely has knowledge of the secret numbers, but Peggy and Victor may repeat this process with different values of r, α, and b1...bk until Victor is assured that Peggy has the correct s1...sk.

To see how this scheme fulfills all the requirements of a zero-knowledge proof, consider a slightly simpler version, where x ≡ r2 mod n (this was the original scheme, but is not quite zero-knowledge as one bit{the sign bit{could be determined by Victor or Eve, because x must be positive). Since we have vi ≡ si2 mod n, it is clear that y2 ≡ r2 × s1b1 s2b2 ...skbk mod n ≡ x × v1b1 v2b2 ...vkbk mod n for the correct set of secret numbers, thus the proof is complete.If Peggy does not have si...sk, she can only compute y ≡ r, which will pass Victor's check with probability p = 1/2k, because it will only be successful in the case where all k bits are zero. Therefore the proof is sound. Finally, Victor or Eve are unable to compute si...sk from any of Peggy's communications, because as previously mentioned, the modular square root is hard to compute.The only difference - the inclusion of the sign bit s makes is to remove a limitation on vi: instead of being limited to positive squares mod n, if vi can be plus or minus a square mod n, Victor and Eve now have less information on the possible values of si. Assumptions of Security and Possible AttacksThe security of this protocol relies on the probability of Eve successfully impersonating Peggy (or Peggy proving to Victor that she knows s1...sk without really knowing them) being very small. In fact, if the identification scheme is repeated t times, the soundness error is p = 1/2kt (each time with independent error 1/2k). The authors Fiege, Fiat, and Shamir suggest taking k = 5 and t = 4; with these values, p is less than a one-in-a-million chance.One of the known attacks on Fiege-Fiat-Shamir (FFS) identification is called a middleman attack, and is a threat to any zero-knowledge proof. It works like this: if dishonest middleman Mark can access the connection between Peggy and Victor, he's able to relay Peggy's communications to Victor and Victor's responses, so that when Victor verifies Peggy's knowledge, it's through Mark. Mark is the one who's identified as the correct user. The countermeasure typically used to protect against middleman attacks is a time limit on each response, which is too short to allow for the relay of communications.A more complicated attack on FFS identification is known as fault analysis. In this scenario, suppose Victor wants to find out not only that Peggy possess secret numbers s, but also the value of s. After he's sent v ≡ s2 mod n, he may purposefully induce a fault E in Peggy's randomly generated value r, so that r becomes r+E. Now, the scheme is executed as usual, with x’ ≡ (r + E)2 mod n and y’ ≡ (r + E)2 × sb mod n.It's then possible for Victor to try both possible values of α in computing Peggy's randomly chosen r, as r ≡ (2E)-1 ((c+E)2-E2) ≡ (2E)-1 (αr-2 ×sb) mod n, and he can check whether he has the correct r by the equivalence x0 ≡ (r + E)2 mod n. Once Victor has the value of r, he is able to compute sb ≡ (r + E)-1 × y’. Don’t worry if these calculations are difficult to follow; the important takeaway is that faults allow Victor to figure out Peggy’s secret numbers, which means the protocol is no longer zero-knowledge.There are a variety of measures implemented to prevent against fault analysis. Peggy could refuse to respond to very simple challenges b from Victor, since these make it easier to perform fault analysis. Additionally, Peggy could repeat operations to check that their results are the same and no fault has been introduced, add error-checking bits data to prevent a fault being introduced, or improve hardware to resist faults.Now that we’ve learned about the inner workings of an important cryptographic technique, the next time you use a digital certificate or digitally sign a document, you’ll know what’s really going on at the mathematical level.