Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently

Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently

Marek Jawurek and Florian Kerschbaum and Claudio Orlandi
ACM CCS 2013 [pdf] [bibtex]

Zero knowledge (ZK) proofs are a special case of 2PC, and are meaningful only when providing security against malicious prover. Hence, one can use any cut-and-choose-based protocol to obtain a secure ZK protocol.

Viewing ZK proofs as special cases of 2PC functionalities, we see that only one party (the prover) gives input. This paper gives an efficient garbled-circuit-based protocol for such functions, where only one party has input.

The high-level protocol works as follows. Let Alice denote the party who has input ⚠ {$x$}, where the parties would like to compute output ⚠ {$f(x)$}.

  1. Bob generates a garbled circuit for ⚠ {$f$}.
  2. Using OT as in the standard Yao protocol, Bob sends Alice the garbled input corresponding to her input ⚠ {$x$}.
  3. Bob sends the garbled circuit to Alice
  4. Alice evaluates the garbled circuit to obtain garbled output ⚠ {$Y$}. She commits to the garbled output.
  5. Bob opens the garbled circuit so that Alice can verify that it was generated correctly.
  6. If the garbled circuit was generated correctly, Alice opens her commitment to ⚠ {$Y$} and Bob decodes the output.

Security is argued in the following way:

  • Suppose the garbling scheme has the authenticity property of BHR12. Then given a garbled circuit and one garbled input corresponding to ⚠ {$x$}, it is infeasible to generate a garbled output ⚠ {$Y'$} that decodes to anything other than ⚠ {$f(x)$} or ⚠ {$\bot$}. Hence, the value ⚠ {$Y$} in the protocol is "proof" that Alice was able to make ⚠ {$f$} output ⚠ {$f(x)$}.
  • However, if the garbled circuit was generated incorrectly, then the garbled output ⚠ {$Y$} may leak too much information about Alice's input ⚠ {$x$}. Opening the circuit allows Alice to check whether the circuit was generated correctly, but it allows Alice to learn all of the output wire labels, so breaks the authenticity property above. This is resolved by having Alice commit to ⚠ {$Y$} in step 4. At the time she is committed, the authenticity property holds. She does not reveal ⚠ {$Y$} until she is convinced that the circuit is garbled correctly, which guarantees that ⚠ {$Y$} leaks no more information than the output ⚠ {$f(x)$}.
  • This protocol requires a "committed" variant of OT. Step 2 must commit Bob to the garbled input wire labels, which are revealed in step 5.

Interestingly, the protocol does not require the standard privacy property of garbled circuits. The garbled circuit does not need to hide the intermediate values of the circuit from the evaluator Alice, since she knows the entire input to the circuit.

Overall, this protocol gives malicious security at the cost of a single garbled circuit.

Categories:

SpecialPurpose