I encountered the use the following protocol as a zero-knowledge proof (argument?) of knowledge of x given y=g^x for a typical DL group:

  1. Verifier chooses c and sends g^c
  2. Prover responds with g^(cx)

It is simpler and more efficient than Schnorr. Intuitively it seems satisfactory. It is zero-knowledge (can be simulated) and I cannot come up with a strategy for responding without knowing either x or c in advance.

That said, I cannot write an extractor for it (and if one did exist, it seems it would break DH key exchange). So it is not provably sound but let's pretend this fact isn't enough to scare me away. I am wondering if anyone can shed more light on why it might be problematic to do this in practice.

  • $\begingroup$ Suppose you choose a random $y$, for which you don't know $x$ such that $y=g^x$. Can you convince the verifier that you DO know $x$? $\endgroup$ Nov 18 '16 at 18:16
  • $\begingroup$ As explained by poncho, that protocol is not zero-knowledge. ​ More generally, 2-move protocols without setup can't be zero-knowledge. ​ ​ ​ ​ $\endgroup$
    – user991
    Nov 18 '16 at 22:58
  • $\begingroup$ eprint.iacr.org/2006/337 $\endgroup$ Nov 19 '16 at 12:59
  • $\begingroup$ There's no extractor so this protocol is not a proof of knowledge. $\endgroup$ Nov 19 '16 at 13:19

why it might be problematic to do this in practice.

One issue with it is that it potentially allows the attacker an Oracle to the cDH problem.

For example, suppose the Prover uses his $g^x$ value as his key share with a DH key exchange with Alice, who sends $g^a$, and both sides arrive at the $g^{ax}$ secret value.

Then, what your protocol would allow an evil Verifier to do is ask the Prover to prove that he knows $x$, and submits $g^a$ (or a blinded version) as his challenge; the Prover sends back $(g^a)^x$, and that gives away the secret value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.