Ryfujk

The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK).

However, I can't figure out why this simple protocol, which is actually just a Diffie-Hellman key establishment protocol, is not an HVZKPoK also
(I understand that if it would be the case, I would see it everywhere in literature as an example of HVZKPoK).

Common input: generator $g$ of group $G$;

Prover's input: secret random $x$, and $y=g^x$;

Verifier's input: $y$;

Verifier is getting proof that the prover knows $x$ so that $y=g^x$ in 2-steps protocol:

1. Verifier $V$ selects randomly $k$, and sends $v = g^k$ to the prover.


2. Prover evaluates $r = v^x$ and sends it to the verifier.


3. Verifier accepts iff $r = y^k$.

Completeness of this protocol is obvious.
Soundness is based on the assumption of hardness of Diffie-Hellman problem.

Honest-verifier zero-knowledgeness seems easy to show: in order to simulate correct transcripts, simulator just selects random $k$, and outputs $(g^k, y^k)$ as a valid transcript.

Could you point me to a mistake in my logic, or assert that this protocol is correct HVZKPoK (in the latter case, why it's not preferred than Schnorr one).

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most situations.

1. The soundness of the protocol is not based on the Diffie-Hellman problem.

This is probably the most important point to address. What does it mean for this protocol to be sound? Informally, soundness can deal with two types of statements: you might want to prove membership in a language, or (this is stronger) you might want to prove knowledge of a witness. An example of the first statement could be "I claim that $(g,h,u,v)$ is a DDH-tuple", while an example of the second statement can be "I know the discrete logarithm of $y$ in base $g$".

Let's go back to your protocol now: you should be easily convinced that it cannot be expressed as a statement related to membership to some language: this would be a trivial statement (think "$y$ does have a discrete log in base $g$": if $g$ is a generator, this is always trivially true). What you truly care about is showing that the prover does know the discrete log of $y$ in base $g$. Formally, I know a witness is defined in cryptography as the witness can be efficiently learned from me, or more precisely: there exists a polynomial-time extractor that, given the code of the prover, can extract a valid witness from the code.

Now, how would you do that with your protocol? With Schnorr's protocol, it's fairly easy: given the code of the prover, run it to get the first flow $g^r$, then put a breakpoint, fork it, and run it twice on two different challenges $e,e'$ from the verifier. You get back two answers $d,d'$ which satisfy (with non-negligible probability) the verification equation: $y^ecdot g^r = g^d$ and $y^{e'}cdot g^r = g^{d'}$. From the two equations, you easily get $g^{(d-d')cdot (e-e')^{-1}} = y$ (assuming you have a prime order group), hence you've just extracted the witness $x = (d-d')cdot (e-e')^{-1}$.

I would suggest that you spend a minute or two convincing yourself that there is no clear way to do the same thing with your protocol. Given the code of the prover, it is not clear at all how one would extract $x$.

But now, this is unsatisfying, right? Intuitively, it seems clear that the only way for the prover to answer correctly the challenge of the verifier in your protocol is by knowing $x$. This seems obvious, but we cannot prove it. This issue has been acknowledge long ago in the crypto community - it was first identified by Damgård in this paper, published in 1991. The best cryptographers could do was to formalize this belief in the form of an assumption, which is called the Knowledge-of-Exponent Assumption (KEA). This assumption states exactly that our intuition must be right: "for any polytime algorithm A that successfully replies (with good probability) with $y^k$ given as input $g^k$, there exists a polytime extractor that, given the code of A, outputs $x$ such that $g^x = y$."

Assumptions of this style are now widely used in cryptography - for example, very similar assumptions are at the core of SNARGs and SNARKs, which have gained a widespread attention due to their efficiency and their use in anonymous cryptocurrencies. Still, they are weird assumptions. For one thing, they are not even falsifiable: to break the factorization assumption, just give me a polytime algorithm that factors number, and I can easily check that it works. But for KEA, it's not even clear how one could verify that you have broken the assumption - this cannot just be an efficient algorithm, it has to be somehow an algorithm, together with a convincing argument that no extractor can exist for this algorithm.

Getting back to your protocol, then: it is believed to be sound, but only under the KEA assumption (tautologically). This is a weird and not well understood assumption. It does not even come close to being comparable to the Diffie-Hellman assumption, it's just a strange object in itself. In comparison, note that the soundness of Schnorr's protocol is just unconditional. Not based on a weird assumption, but also not even based on an assumption at all.

2. The protocol is only HVZK, not ZK, and it is not clear how to make it ZK

Before moving on with this point, a quick digression: a simple modification of your protocol can be used to prove that a tuple is a DDH tuple (meaning: fix generators $(g,h)$, and now the prover wants to demonstrate that some pair $(u,v)$ is of the form $(g^x,h^x)$). Proving DDH relations is widely used in crypto. But unlike your protocol, we can now be happy with a membership proof: in most situations, it suffices to show that the witness $x$ exist (it's a non-trivial relation), no need to show that the prover knows it. So, suppose you modify your protocol as follows:

Verifier: send $g^{k_1}cdot h^{k_2} = w$

Prover: answer with $z = w^x$

Verifier: check that $u^{k_1}cdot v^{k_2} = z$

Then, interestingly, the previous issue disappears entirely: although it would still require KEA to prove that the prover must know $x$, it does not require any assumption at all to prove that $x$ exists, and this suffices to show that $(u,v)$ is a DDH tuple! In other words: in appropriate settings, for a slightly different language, a variant of your protocol does actually not have any problem with soundness anymore. So, why do we still not use it often?

This has to do with zero-knowledge. As you correctly pointed out, your protocol (and the variant above) satisfies honest-verifier zero-knowledge (as does Schnorr's protocol), meaning that it is zero-knowledge as long as the verifier is honest.

Sure, but why do we even care about HVZK? In practice, we are not really happy with something being secure only when the opponent is honest, right? The answer is that what we truly care about is indeed full-fledged ZK, but HVZK is often a good first step: we know very general and very efficient transformations that can convert a large class of HVZK protocols into full-fledged ZK protocol. Hence, we can just build HVZK protocols, prove that they satisfy this property, and they can be compiled into real ZK protocols when needed.

What is this large class of HVZK protocols that we can transform efficiently into ZK protocols? They are the so-called public coin protocols: all protocols in which all the randomness used by the verifier is fully revealed to the prover. Take one minute to convince yourself that this property is satisfied by Schnorr's protocol (and by essentially any HVZK protocol in the literature, up to a few exceptions), but not by your protocol. This means that even though your protocol is HVZK, this does not suffice to make it ZK through general techniques!

Of course, there are known methods that can transform your protocol into a ZK protocol, introducing additional rounds and complexity. But then, they end up loosing any clear advantage over Schnorr's protocol in terms of efficiency... So we usually simply stick to Schnorr and its variants :)