Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation

Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation

Payman Mohassel, Ben Riva
CRYPTO 2013 [pdf] [bibtex]

Several new approaches are presented for dealing with the major challenges of the cut-and-choose technique:

Output Authenticity

A natural way to ensure output authenticity for the sender's output is for the receiver to simply send the output wire labels, since the receiver cannot falsify these wire labels (the "authenticity" property of BHR12). However, this is problematic because the receiver cannot reveal to the sender which of the evaluated garbled circuits was among the majority. The solution is to ensure that all garbled circuits are generated with the same output wire labels, yet this leads to the problem that opening circuits for the cut-and-choose will reveal both wire labels, compromising the authenticity property.

This work suggests to carefully order the steps of the cut-and-choose mechanism:

  1. Choose the circuits to be checked/evaluated.
  2. Evaluate the circuits and commit to the majority output wire labels.
  3. Open the check circuits and verify that they are all correct and share the same output wire labels.

Importantly, the receiver commits to the output wire labels while the authenticity property still holds, and reveals the output only when the cut-and-choose is complete.

Input Consistency

Input consistency is achieved via the following approach. First, the parties evaluate the many circuits of the form ⚠ {$C(x\|r_i, y) = (f(x,y), x \oplus r_i)$}, with Alice acting as the sender. The parties also evaluate many circuits of the form ⚠ {$C'(x\|r_i) = x \oplus r_i $}, with Bob acting as the sender. Alice is meant to use the same ⚠ {$x$} in all circuits, and matching values of ⚠ {$r_i$} for the two sets of circuits. The following checks can ensure that the same ⚠ {$x$} is used in each circuit ⚠ {$C$}:

  • Alice picks up the garbled inputs for all of the ⚠ {$C'$} circuits via a single OT from Bob, so she can be forced to use the same ⚠ {$x$} in all of these.
  • The parties can check that the ⚠ {$x \oplus r_i$} outputs match between corresponding pairs of ⚠ {$C$} and ⚠ {$C'$}.
  • The cut-and-choose is altered in the following way. For every garbled circuit ⚠ {$C$}, Alice also sends wire lables for her ⚠ {$r_i$} values. Then, Alice uses OT to pick up her wire labels for the ⚠ {$r_i$} values in the ⚠ {$C'$} circuits. Only after this, the parties do a cut and choose on the ⚠ {$C$} circuits. For each opened circuit, Alice also reports her garbled input for the corresponding ⚠ {$r_i$} in the corresponding ⚠ {$C'$} circuit. At this point, the authenticity of wire labels ensures that Alice cannot falsify the wire labels for ⚠ {$C'$} garbled circuits. Hence, Bob can check that, at least in every opened ⚠ {$C$} circuit, Alice was committed to using the same ⚠ {$r_i$} that she used in the corresponding ⚠ {$C'$} circuit.

Combining these three checks, Bob can be convinced that the same ⚠ {$x$} is used in the majority of unopened ⚠ {$C$} circuits, with high probability.

Covert Security

A new variant of covert security is presented. As usual, a cheating adversary is caught with some guaranteed probability. In this new model, however, the adversary learns only a single bit and cannot violate correctness even if cheating is undetected. In the original covert security model, the adversary would violate all security properties in the case that cheating is undetected.

A variant of the dual execution protocol of MF06 is presented that achieves this definition with deterrence factor ⚠ {$\epsilon$} using ⚠ {$2/\epsilon$} circuits total. Another variant is described using ⚠ {$O(\log(1/\epsilon))$} circuits.

Other links:

CRYPTO presentation slides (PPTX)

Categories:

CutAndChoose SecurityModels