search

jancarlsson / snarklib

a C++ template library for zero knowledge proofs
Other
49 stars 11 forks source link

multiAND/multiOR info leak #2

Closed apulsifer closed 9 years ago

apulsifer commented 9 years ago

I'm confused by the comment that multiAND and multiOR leak information when zbit = 1. It is my understanding that in zero-knowledge proofs, the constraint system is supposed to be known to both the prover and the verifier. The verifier needs to know the prover's constraints in order to know that the system of equations was satisfied. Therefore, knowledge of whether a set of bits should AND to 0 or 1 is already part of the shared knowledge in the system, and if it shows up in the constraints (which it must in order for the proof to be valid), that has not leaked any of the prover's private information. (In addition BTW, I'm not sure zbit = 1 makes any difference--the presence of the 1 in the constraints should say just as much as the absence of the 1.) Could you clarify how "incorporating the witness in the constraint system" leaks the prover's private information (other than the information that the prover's private values satisfy the constraints, which is not private information--that is what the prover is trying to prove).

apulsifer commented 9 years ago

PS, Sorry I meant to post this to snarkfront, not snarklib. I can close the comment here and move it there if you like...

jancarlsson commented 9 years ago

It's ok to leave the comment here.

The value of zbit changes the generated constraints. Proving a true output value for a logic gate is not the same as proving a false output value. That isn't too surprising. It's like two functions with different roots.

What you say is true. The prover and verifier both know the constraint system, public inputs, and expected output value of the logic gate. If that output value is part of the hidden witness known only to the prover, then revealing it in the structure of the constraint system leaks knowledge. So how can this work?

Note that zbit always takes a literal value when multiAND and multiOR are called. The value of zbit must be known to all parties. Therefore, it can not depend on private knowledge known only to the prover. Instead, it depends on declarative conventions of the EDSL.

For example, the assertion of == means "all must be the same" which corresponds to multiAND with zbit = true. Prover and verifier both agree on this assertion of equality. It is exogenously baked in to the constraint system.

So... how does this explain "incorporates witness in contraint system"? I wrote the comment after realizing this subtle distinction between exogenous problem structure and endogenous solution. Here's another analogy. A multiple choice test with more choices for problems is "more secure" against the random guessing strategy. These ZKPs are finite like a multiple choice test. If the structure of the arithmetic circuit (constraint system) limits the number of choices, it is easier for the prover taking the test. Soundness is weaker (guessing is more likely to pass verification). That is what I meant by "incorporates the witness."

jancarlsson commented 9 years ago

The more I looked at "incorporates witness in constraint system", the less sense it made. In fact, it confused me just as it did you. The comments for multiAND and multiOR have been changed (snarkfront file R1C.hpp).

Thank you for posing this question. To answer it, I was forced to think deeper.