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:
- Verifier chooses c and sends g^c
- 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.