Zero Knowledge Identification and One-Way Homomorphisms

Imagine logging into a secure web server which, instead of asking you to type in your password, merely asks you questions about your password until it’s convinced that you really do know it and therefore are who you say you are. Moreover, imagine that your answers to the server’s questions provide no information whatsoever which could be used by a malicious hacker, even if all communications between you and the server are being intercepted. Finally, imagine that the server in question not only does not store any information about your password, it has never at any point asked you for information about your password.

Sounds too good to be true, right?

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

The Parable of the Mismatched Socks

You wake up on April 1st and put on what you believe is a pair of red socks; however, being color-blind you aren’t 100% sure. Your wife takes one look at you and says, “Christmas isn’t until December, you know.” You realize that either you accidentally put on one red sock and one green one, or your wife, who is a well-known enthusiast for April Fool’s pranks, is taking advantage of your color-blindness to play a trick on you. In a flash of brilliance, you come up with the following method for testing your wife’s truthfulness:

First, you take off the socks, place one in each hand, and ask your wife to remember which one is where. Then:

(1) You place your hands behind your back and secretly either switch the socks between your hands or leave the socks where they are.

(2) You bring your hands in front of you and ask, “Did I switch hands?”

She answers correctly. So you repeat steps (1) and (2) again. She gets it right once more. You repeat steps (1) and (2) eighteen more times, for a total of 20 questions, randomly selecting each time whether or not to switch the socks. And she gets it right every single time.

Assuming you haven’t been married so long that she can simply anticipate all of your random choices, there are only two possibilities here: either the socks really are different colors or she was just guessing every time and got extremely lucky. The chances of the latter are 1 in 2^{20}, or about one in a million. You decide that your wife is not, in fact, taking advantage of your color-blindness as a cruel joke but is genuinely trying to save you from public embarrassment.

Zero Knowledge Proofs

Aside from the remarkable fact that you’re completely color-blind and yet your wife has managed to convince you that your socks are mismatched, there’s another interesting feature of this thought experiment: at no point have you been given any information about which sock is red and which one is green. This is — morally speaking, anyway — the idea behind a zero knowledge proof.

A Mathematical Implementation

This is fascinating, but it doesn’t seem to have much to do with our original problem concerning computer passwords. So let’s see how to implement the idea behind the thought experiment in a more abstract mathematical way.

A group is a set G together with a binary operation \ast : G \times G \to G satisfying a few simple axioms. In particular, there should be an identity element e \in G with e \ast x = x \ast e = x for all x \in G, and for every x \in G there must be an element x^{-1} with x \ast x^{-1} = x^{-1} \ast x = e.

If G and H are groups, a homomorphism from G to H is a function f : G \to H such that f(e_G)=e_H and f(x \ast_G y) = f(x) \ast_H f(y) for all x,y \in G.

We’ll call a group G computable if x \ast y and x^{-1} can be efficiently computed for all x,y \in G.

A one-way homomorphism is a homomorphism f : G \to H such that (a) f(x) can be efficiently computed for all x \in G; but (b) f is hard to “invert”, in the sense that given a random element y \in H it is computationally infeasible to compute an element x \in G with f(x)=y.

Here are some classic examples of one-way homomorphisms which are frequently used in cryptography:

(1) Let p be a large prime number, let g be a primitive root modulo p, and let f : ({\mathbb Z}/(p-1){\mathbb Z},+) \to (({\mathbb Z}/p{\mathbb Z})^\times,\cdot) be the map sending x (considered as an integer modulo p-1) to g^x modulo p. The value of f(x) can be computed efficiently for every x via the method of successive squaring, but computing x given f(x) is the famous discrete logarithm problem.

(2) Let n = pq where p,q are large prime numbers, and let f : (({\mathbb Z}/n{\mathbb Z})^\times,\cdot) \to (({\mathbb Z}/n{\mathbb Z})^\times,\cdot) be the map sending x to x^2 modulo n. This is a one-way homomorphism (assuming that factoring is hard), because if we had an efficient algorithm to compute a square root of any y \in ({\mathbb Z}/n{\mathbb Z})^\times we could use this algorithm to factor n (see Concluding Remark 2 below.)

Suppose, then, that we’re given a one-way homomorphism f : G \to H between computable groups and that Peggy selects a random element s \in G as her secret password. (Technical note: We need to assume that we have an efficient algorithm for selecting a random element of G; this is certainly the case in the two examples above.) Peggy makes the value S = f(s) public; anyone who cares is allowed to know the value of S.

Here’s how Victor (the verifier) can verify that Peggy (the prover) knows the password s, without compromising the fact that s must be kept secret:

(1) Peggy generates a random element r \in G and sends R = f(r) to Victor.

(2) Victor flips a fair coin. If it comes up heads, he asks Peggy to send him the value of r; if it comes up tails, he asks Peggy to send him r \ast s.

(3) Once Peggy sends the requested value r', Victor verifies (if it was heads) that f(r') = R or (if it was tails) that f(r') = R \ast S. Since f is a homomorphism, if Peggy is telling the truth then Victor’s verification procedure will work.

Peggy and Victor now repeat steps (1)-(3) some number of times. As we will see, if they run through this procedure k times and the verification checks out each time, the probability that Peggy is in fact a malicious hacker who does not actually know the value of s will be at most 1 / 2^k. So if k = 20, for example, there is less than a one in a million chance that Peggy does not actually know the password.

Security Analysis

Why is it difficult for someone who doesn’t know the password to answer the queries correctly? And why do Peggy’s responses not provide Victor (or anyone eavesdropping on their interaction) with any information about the value of s?

Let’s answer the second question (the “zero knowledge” part) first. If Peggy chooses a random r and sends it to Victor, this clearly does not provide any new information about the value of s. And that’s exactly what happens when Victor’s coin flip comes up heads. On the other hand, if the coin flip comes up tails, Peggy sends the value of r \ast s. However, since r was chosen randomly, the value of r \ast s will also be completely random. So in either case, Peggy is not revealing any information about s itself to Victor or anyone else.

For the first question, we need to suppose that Peggy is in fact a malicious hacker and place ourselves in her shoes. How could she attempt to get every question correct without knowing the value of s or having an efficient algorithm to invert the function f? Well, if Peggy can anticipate Victor’s coin flips, then whenever he is about to flip “tails”, Peggy can report R' = f(r) \ast S^{-1} instead of R = f(r) and r' = r instead of r \ast s. This does not require knowledge of s, and Victor will certify Peggy’s response as correct since f(r') = f(r) = R' \ast S.

However, if Victor’s coin flips are truly random then Peggy cannot use this strategy. In order to account for the possibility that Victor might flip heads, she needs to legitimately report R as f(r). But if Victor flips tails, Peggy will then be stuck needing to produce the value of r \ast s given r, which clearly requires knowledge of s.

Concluding Remarks

1. Zero-knowledge proofs were first introduced in this 1989 paper by Goldwasser, Micali, and Rackoff. The abstract protocol introduced here (in the special case where f(x) = x^2 \pmod{n}) is a simplified version of the Feige-Fiat-Shamir identification scheme. The case of our abstract protocol in which f(x) = g^x \pmod{p} originated (as far as I can tell) with this paper. The thought experiment involving color-blindness is frequently used to illustrate zero-knowledge proofs, but usually with balls rather than socks. I read the “sock” version in this expository paper by Antoine Chambert-Loir.

2. To see that if we had an efficient algorithm to compute a square root of any y \in ({\mathbb Z}/n{\mathbb Z})^\times we could use this algorithm to factor n, take a random x, square it, and use the algorithm to find one of the four square roots of x^2 modulo n. After repeating this a number of times, with high probability we will find x' \not\equiv \pm x \pmod{n} such that x^2 \equiv (x')^2 \pmod{n}. The GCD of x-x' and n will then be equal to either p or q.

3. In practice an interactive “query and response” protocol of the above type can be inconvenient. Using a suitable cryptographic hash function, one can reduce any such protocol to a non-interactive one using the so-called Fiat-Shamir heuristic.

4. Another example of a one-way homomorphism is the map {\mathbb Z} \to E({\mathbb F}_q) sending n to nP, where E({\mathbb F}_q) is the set of {\mathbb F}_q-points of a suitable elliptic curve over a large finite field {\mathbb F}_q and P \in E({\mathbb F}_q) is a point of large order (e.g. a cyclic generator). Cryptographers have proposed and studied many other interesting examples. I’m not sure if it’s useful to allow the groups G and/or H to be non-abelian, but I noticed while writing up this post that (unlike in discrete logarithm-based key exchange protocols such as Diffie-Hellman) commutativity is not needed for the kind of zero-knowledge identification schemes discussed here.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s