# Zero Knowledge Example using discrete log

I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic.

Since the Verifier is given p, g and y, where p is a large prime, g the generator and y = g x mod p. The value x is secret. My problem is that that there is leakage of information since y depends directly on the secret x.

Alternatively, the security is that of the discrete algorithm problem. Is this a poor example or do all realizable ZKP leak information?

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the Prover sends; it is a given. The base problem consists in (p,g,y) and what the Prover tries to demonstrate is that he knows the corresponding x -- but without helping the Verifier find out x.

The Verifier can always try to solve the problem by himself. This is in fact unavoidable: since a ZK proof is about proving knowledge of a solution to a given problem, anybody can, conceptually, try to solve the problem upfront, if only by exhaustive search of all possible bit patterns for a solution.

This does not count as a leak because it is not information obtained from the Prover. It is part of the context. It is information that everybody already has. The whole of ZK is about demonstrating knowledge of some value without yielding extra information that was not already public knowledge.

(Honestly I never understood why the cave example was all the rage. It is an analogy and it breaks down when looked at too closely. For instance, Victor could say to Peggy: enter the left corridor, and exit from the right one. This would demonstrate that Peggy knows how to open the door, and would be vastly simpler than the pseudo-ZK concocted for that example.)

Zero knowledge property here is simulator availability that produces indistinguishable protocol transcript. In other words, proving party can deny being ever engaged in a protocol.

One would use Pedersen commitments to avoid leaking any information about his secret.

From y you don't get any information about x, because of the 'mod p' part, which makes the result y random.

• This is so wrong; given $g$, $p$, $g^x \bmod p$, it is easy for a computationally unbounded adversary to recover $x$. We believe it is infeasible for a practical adversary to do it if we select $g$, $p$ correctly; however that's because the algorithms we know require more computation than we have at our disposal; the information is all there -- we just don't know what to do with it. – poncho Nov 7 '14 at 15:43
• Well, if you assume a computationally unbounded adversary then many problems (DDH, CDH) become easy which are used in security reduction of many cryptographic protocols. – Bitswazsky Nov 7 '14 at 15:53
• You stated that 'you don't get any information about x, because ... the result y [is] random"; that is a claim about informational security -- I just mentioned that it is not accurate. And, in any case, this really isn't an answer to the question; see Thomas's response for the correct answer ("it isn't that $g^x \bmod p$ doesn't leak any data, but that a ZKP doesn't leak any additional information") – poncho Nov 7 '14 at 16:05
• @sayan, then you should state your assumption on computationally bounded adversary as "don't get any information" sounds like you are talking about information theoretic security (i.e., computationally unbounded) – mikeazo Nov 7 '14 at 16:06
• Okay, I admit, I should have mentioned that. – Bitswazsky Nov 7 '14 at 16:08