2 ms·

Zk proofs shouldn't leak knowledge to cheating provers or verifiers. Sometimes the verifier has access to a secret, and just needs to confirm the prover does as

Zk proofs shouldn't leak knowledge to cheating provers or verifiers. Sometimes the verifier has access to a secret, and just needs to confirm the prover does as well. We're stretching what was supposed to be a useful analogy pretty far here. The idea was that the knowledge of details about your mother can act as a proxy for the secret, experiential knowledge of having met her, which is not current shareable between humans. If the verifier picked good questions, asks enough of them, and never reuses them, this is a decent approximation of the functionality of a zk proof. Anyway, we're off the rails, but one thing I know is that I'm proud no one on HN has made a "your mom" joke yet. Kudos all around.

betterunix2 9y ago
"Zk proofs shouldn't leak knowledge to cheating provers or verifiers." It is trivial to show that ZK proofs leak nothing to the prover: the verifier has no secret input to leak. This is somewhat technical but it comes down to the actual definition of ZK, which is that for any verifier V, there exists an algorithm S that has the same output distribution as V but which never interacts with the prover (at least in the case where the proof is valid). The existence of that algorithm implies that the verifier "learns nothing" -- because whatever it can compute after the interaction is something it could have computed a priori. As a result, whatever inputs the verifier has cannot actually impact the proof itself -- otherwise it would be impossible to satisfy such a requirement. Using your example, suppose the prover can only succeed if its secret input is equal to the verifier's secret input. No algorithm that does not interact with the prover could have the same output distribution as the real verifier, because that distribution will depend on the prover's input (i.e. whether or not the input is equal to the verifier's). So you cannot actually accomplish that task with a zero knowledge proof; or taking the contrapositive, the verifier has no secret inputs in a ZK proof. (If you are wondering what the verifier would "learn" in such a situation, one answer would be a transcript of the interaction itself.) So, if we were to try to apply the ZK definition to the prover, we would have something trivial: take the prover P and run an "internal" copy of P in some bigger algorithm that does not interact with the verifier. Since there is no secret verifier inputs, that bigger algorithm can just follow the protocol and output whatever P outputs. Since the protocol is just being followed exactly, P has no way to distinguish the simulation from the real interaction, so the output distribution is unchanged. In other words, the prover necessarily learns nothing from the protocol.

betterunix2 9y ago

"Zk proofs shouldn't leak knowledge to cheating provers or verifiers." It is trivial to show that ZK proofs leak nothing to the prover: the verifier has no secret input to leak. This is somewhat technical but it comes down to the actual definition of ZK, which is that for any verifier V, there exists an algorithm S that has the same output distribution as V but which never interacts with the prover (at least in the case where the proof is valid). The existence of that algorithm implies that the verifier "learns nothing" -- because whatever it can compute after the interaction is something it could have computed a priori. As a result, whatever inputs the verifier has cannot actually impact the proof itself -- otherwise it would be impossible to satisfy such a requirement. Using your example, suppose the prover can only succeed if its secret input is equal to the verifier's secret input. No algorithm that does not interact with the prover could have the same output distribution as the real verifier, because that distribution will depend on the prover's input (i.e. whether or not the input is equal to the verifier's). So you cannot actually accomplish that task with a zero knowledge proof; or taking the contrapositive, the verifier has no secret inputs in a ZK proof. (If you are wondering what the verifier would "learn" in such a situation, one answer would be a transcript of the interaction itself.) So, if we were to try to apply the ZK definition to the prover, we would have something trivial: take the prover P and run an "internal" copy of P in some bigger algorithm that does not interact with the verifier. Since there is no secret verifier inputs, that bigger algorithm can just follow the protocol and output whatever P outputs. Since the protocol is just being followed exactly, P has no way to distinguish the simulation from the real interaction, so the output distribution is unchanged. In other words, the prover necessarily learns nothing from the protocol.