Mfcttrf

I’m trying to wrap my head around zero knowledge proofs, but I’m having trouble understanding it.

In my current understanding, zero-knowledge proofs prove to the recipient that the sender has a certain knowledge without disclosing it. Like trying to say your password without actually giving it.

Many sources go at it with a convoluted method like a tunnel where there’s a hidden gate, and Bob is trying to know if Alice can go through the hidden gate. But then it starts saying that Bob should not see Alice enter. Wouldn’t it be easier for Bob to just see Alice go in one tunnel and come out the other? That would not disclose the secret way of opening the tunnel, right?

In that line of thinking, given a one-way function like a hash, couldn’t the other person just hash their secret and let the other see that the hashes compare?

I must be missing something (as there’s a lot of research going into it and hashes are well-known), but I can’t wrap my head around it.

Can someone tell me what’s wrong with my understanding of zero knowledge proofs?

There are three issues in your proposal, which I'll go over one by one; I hope this will clarify the concept.

The first issue is that the purpose of a zero-knowledge proof is not only to prove knowledge of some information without disclosing it, but something much, much more powerful: the goal is to prove that you know some information$^1$ without disclosing anything at all beyond the fact that you know this information. The point here is that you have no idea what your opponent is going to do with the information you leak about your secret value. It might well be that even some apparently harmless leakage can allow your opponent to do something unexpected and bad. Consider the authentication protocol you suggest, with a hash function $H$: here, given a secret value $v$, you leak $H(v)$. This is clearly not "no information", and you have no guarantee that this $H(v)$ cannot be used to do something bad. So, the way we define zero-knowledge proof aims at anticipating every possible scenario, as follows: we say that the protocol is zero-knowledge if there exist an efficient algorithm that could produce an interaction with the verifier which is indistinguishable from an honest interaction, but without knowing the secret value. The intuition between this definition is that if the transcript of the interaction cannot be distinguished from something that could have been produced without even knowing the secret value, then it cannot convey anything useful about this value to the verifier (of course, defining that formally requires some care). Your protocol clearly does not satisfy this.

The second issue is the generality of the functionalities we want to consider in general. In your example, you actually assumed that you were only proving that you know the same value as the one already held by your opponent (since she must hash the value herself to compare). But this is not a very useful situation in general. A much more general setting would be for example the following: some public ciphertext $c$ is known, and you want to prove to an opponent that you know its plaintext, but without disclosing the actual plaintext. Here, your hash-then-send simple approach does obviously not work at all. In fact, zero-knowledge proofs deal with even much more general situations than this, allowing to prove wide classes of statements about secret values, which can be hashed, committed, encrypted, signed, or whatever you like.

Eventually, the third issue is that a zero-knowledge proof of knowledge must, well, prove knowledge. A protocol proves knowledge of a value if given the code of the prover, it is actually possible to extract this value efficiently (this is the formal definition of "knowledge" in cryptography). This is also clearly not possible in your example. In fact, your protocol does not prove knowledge of the secret value $v$ at all, since the prover would just have to know $H(v)$ to complete it - which, as you pointed out yourself, does not imply that he knows $v$, since $H$ is one-way.

Let's go over an actual example, to make all of that more concrete.

Take a finite group $G$ of prime order $p$ (I assume some familiarity with basic algebra here). Fix a generator $g$. Consider now another group element $h$. The goal of the prover is to demonstrate to the verifier that he knows a secret value $x$ such that $h = g^x$ (not that such an $x$ exists since $g$ is a generator, but finding it given $h$ might be hard - it's the discrete logarithm problem). This is very useful for authentication: $h$ will be the "public identity" of the prover, and demonstrating knowledge of $x$ such that $g^x = h$ can be used to authenticate him as the owner of the "private identity" associated to $h$ (it's exponent in base $g$). Take one second to convince yourself that no simple "hash based" solution does work here.

Here is a protocol that actually works:
- The prover picks a random exponent $r$ and sends $R = g^r$ to the verifier.
- The verifier picks a random exponent $e$ (the challenge) and sends it to the prover.
- The prover computes and sends $d = ex+r$ to the verifier.
- The verifier checks that $h^ecdot R = g^d$.

Take a few seconds to check that the protocol is correct, meaning, if the prover plays honestly, the check of the verifier will succeed.

Why is this zero-knowledge$^2$? Because one can generate a transcript that is perfectly indistinguishable from a honest transcript of this protocol, but without knowing anything about $x$: pick $(e,d)$ at random, then set $R gets g^d/h^e$, and output the transcript $(R,e,d)$. Note that this can be easily checked to give a transcript uniformly distributed over all transcripts satisfying $h^ecdot R = g^d$ - i.e., uniformly distributed accross all honest transcripts. Therefore, interacting with the prover in this protocol does not convey any information at all about $x$ (since a transcript following the exact same distribution could have been generated without knowing $x$).

Why does this prove knowledge of $x$? To show this, I must show that given the code of a verifier that succeeds in this proof, I can efficiently recover $x$ - hence showing that this prover actually knows $x$. I do it as follows: I run the prover code, to get $R$. Then, I put a breakpoint in the code, fork it, and run it twice on two random different challenges $(e_0,e_1)$ that I choose. The first copy of the code outputs $d_0$, and the second copy of the code outputs $d_1$. Since this is the code of a successful prover, I know that the check passes$^3$, hence I have $(R, e_0, e_1, d_0, d_1)$ such that:

$h^e_0cdot R = g^d_0$

$h^e_1cdot R = g^d_1$

which gives after a few easy manipulations $g^(d_0-d_1)cdot(e_0-e_1)^-1 = h$

Therefore, the value $x$ we are looking for is just $(d_0-d_1)cdot(e_0-e_1)^-1$, and we have successfully extracted it. This concludes the proof.

(1) actually, that's only for the specific case of zero-knowledge proofs of knowledge; in full generality, there are two variants of zero-knowledge proofs, which can be used either to show that some statement is true (existential proof), or that you know a proof of some statement (proof of knowledge). I focus on the latter since it seems to be the one you read about.

(2) in fact it's not truly zero-knowledge, formally it only satisfies a weaker definition known as honest-verifier zero-knowledge, but I omitted this point to simplify.

(3) I'm again hiding some technicalities here, since usually we can only assume that the prover succeeds with some noticeable probability, but it does not make a major difference.