3 ms·

I have a question: when we say, zero-knowledge proofs, they are not really "zero-knowledge" right? Going back to your public-private key example, the way someo

by QML 9y ago

I have a question: when we say, zero-knowledge proofs, they are not really "zero-knowledge" right? Going back to your public-private key example, the way someone proves their identity is by giving you some information that only the private key can generate. However, in the event that the person is not who they say they are, don't the gain some information (that the thing they gave it is incorrect)? A way I see to counter this is to make it indistinguishable whether or not the information was correct to the prover. Instead of saying, "incorrect password", you would give them access to an empty account.

mhluongo 9y ago
Note the verifier doesn't need to share the outcome with the prover- that does, indeed, open certain problems up to enumeration. In schemes that rely on computational assumptions (eg, hashing & signing with a nonce) I don't think that's an issue.
betterunix2 9y ago
The definition of "zero knowledge" is that for any verifier V, there exists an algorithm S that outputs the same distribution as V without any interaction. Since S has no interaction with the prover, its output has no dependence whatsoever on the prover; and since that output follows the same distribution as V, it follows that V cannot "learn" anything from the protocol. Here is a concrete example protocol and proof that it is ZK: The prover P will prove knowledge of a discrete logarithm z for G = g^z. 1. P chooses a random x and sends h=g^x to V. 2. V chooses a random c, r and sends C = g^r h^c to P. 3. P chooses a random s and sends A = g^s to V. 4. V sends (c,r) to P. 5. P checks C = g^r h^c and if the check passes, sends Z = cz+s and x to V. 6. V checks h=g^x and g^Z = A G^c. To prove zero knowledge, we use the following simulator S: A) S performs steps 1-4. B) S rewinds V to step 3 (think of the internal copy of V as a virtual machine; S can take a snapshot etc.). C) Since S already knows (c,r), it picks Z randomly and sends A = g^Z G^(-c), and continues with the remainder of the protocol. Note that A G^c = g^Z G^(-c) G^c = g^Z, so the proof will pass. D) After S sends Z, it outputs whatever the internal copy of V outputs. This simulator works because after Step 2, the verifier is bound to c (the g^r h^c value is a Pederson commitment, which is binding as long as V does not know the discrete logarithm of h). Once S knows c, it can "cheat" to create a valid A,Z despite not having knowledge of the discrete logarithm of G. Since the internal copy of V is "convinced" by the proof, it will output whatever it would have output following a real interaction -- at each step it sees the same distribution of messages it would have seen in the real world (V is not aware of the fact that it was rewound once -- again, think of a VM). As to your question about the prover, note that the prover will never learn anything from the protocol; you can apply similar reasoning and construct a "simulator." For P the simulator is trivial -- since there is no secret inputs for V, the simulator can just follow each verifier step honestly, without ever having to rewind P, and will then output whatever P outputs. Typically that simulator is ignored in the case of zero knowledge proofs because it is trivial.

by QML 9y ago

mhluongo 9y ago

Note the verifier doesn't need to share the outcome with the prover- that does, indeed, open certain problems up to enumeration. In schemes that rely on computational assumptions (eg, hashing & signing with a nonce) I don't think that's an issue.

betterunix2 9y ago

The definition of "zero knowledge" is that for any verifier V, there exists an algorithm S that outputs the same distribution as V without any interaction. Since S has no interaction with the prover, its output has no dependence whatsoever on the prover; and since that output follows the same distribution as V, it follows that V cannot "learn" anything from the protocol. Here is a concrete example protocol and proof that it is ZK: The prover P will prove knowledge of a discrete logarithm z for G = g^z. 1. P chooses a random x and sends h=g^x to V. 2. V chooses a random c, r and sends C = g^r h^c to P. 3. P chooses a random s and sends A = g^s to V. 4. V sends (c,r) to P. 5. P checks C = g^r h^c and if the check passes, sends Z = cz+s and x to V. 6. V checks h=g^x and g^Z = A G^c. To prove zero knowledge, we use the following simulator S: A) S performs steps 1-4. B) S rewinds V to step 3 (think of the internal copy of V as a virtual machine; S can take a snapshot etc.). C) Since S already knows (c,r), it picks Z randomly and sends A = g^Z G^(-c), and continues with the remainder of the protocol. Note that A G^c = g^Z G^(-c) G^c = g^Z, so the proof will pass. D) After S sends Z, it outputs whatever the internal copy of V outputs. This simulator works because after Step 2, the verifier is bound to c (the g^r h^c value is a Pederson commitment, which is binding as long as V does not know the discrete logarithm of h). Once S knows c, it can "cheat" to create a valid A,Z despite not having knowledge of the discrete logarithm of G. Since the internal copy of V is "convinced" by the proof, it will output whatever it would have output following a real interaction -- at each step it sees the same distribution of messages it would have seen in the real world (V is not aware of the fact that it was rewound once -- again, think of a VM). As to your question about the prover, note that the prover will never learn anything from the protocol; you can apply similar reasoning and construct a "simulator." For P the simulator is trivial -- since there is no secret inputs for V, the simulator can just follow each verifier step honestly, without ever having to rewind P, and will then output whatever P outputs. Typically that simulator is ignored in the case of zero knowledge proofs because it is trivial.