Ready to Start Your Career?
August 3, 2016
Zero-Knowledge Techniques and the Fiege-Fiat-Shamir Identification Scheme
August 3, 2016
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:
- 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.
- Peggy chooses a random integer r and random sign α. She computes x ≡ α × r2 mod n, and sends x to Victor.
- Victor chooses a random sequence of k bits b1...bk, and sends b1...bk to Peggy.
- 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.
- 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.