Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries

Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries

Yehuda Lindell
CRYPTO 2013 [pdf] [bibtex]

In previous cut-and-choose mechanisms, the sender sends many garbled circuits, the receiver checks some fraction of them, evaluates the others, and reports the majority output. The receiver must not reveal whether any of the evaluated circuits are found to be faulty (unless the majority of them were faulty), since detecting a faulty circuit might depend on the receiver's input. As a result, these mechanisms require approximately ⚠ {$3s$} garbled circuits to be sent to achieve security level ⚠ {$2^{-s}$}.

This work presents a different approach requiring only ⚠ {$s$} circuits. The main idea is to let the receiver obtain the sender's input ⚠ {$x$} in its entirety if the receiver catches the sender cheating (i.e., constructing faulty circuits). Then with the sender's input in hand, the receiver can simply evaluate the function himself.

If two garbled circuits disagree, then the receiver will receive a wire label encoding 0 and a wire label encoding 1 on the same wire in different circuits. We let this pair of wire labels constitute "proof" of cheating.

Overview: The new protocol works roughly as follows:

  1. The sender sends ⚠ {$s$} garbled copies of the circuit, and the receiver opens each one with probability 1/2. If any check circuit is found to be faulty, then the receiver aborts.
  2. The receiver evaluates the remaining circuits. If all of their outputs agree, then the receiver will take this to be the final output (after doing the following steps). If any of their outputs disagree, the receiver has "proof" in the form of contradictory wire labels.
  3. The parties then run a secondary 2PC protocol (using older techniques, with ⚠ {$3s$} circuits) that does the following. It takes the sender's input ⚠ {$x$} and the set of output wire labels from the previous round, and it takes the purported proof from the receiver. If the proof implicates the sender, then the receiver gets output ⚠ {$x$}, otherwise the receiver gets empty output.
  4. The receiver either outputs the value of the garbled circuits (if they all agree), or else learns ⚠ {$x$} and computes the output directly using ⚠ {$x$} and his own input ⚠ {$y$}.

Intuitively, the only way for the sender to cheat is to have all check circuits be valid and to have all (not just a majority of) evaluation circuits be incorrect (and agree in their output). Since each circuit is checked with probability 1/2, the adversary can succeed with probability at most ⚠ {$2^{-s}$}.

Note that the parties must always perform the secondary 2PC step. The sender cannot know whether the receiver obtain proof of cheating, since that can depend on the receiver's input.

Challenges: The main challenges in getting these intuitive ideas to work include:

  • Ensuring that the sender provides the same input ⚠ {$x$} in both the main and secondary computations. This is done with standard input-consistency techniques.
  • Ensuring that the sender provides the correct wire labels to the secondary computation. This is done by committing to output wire labels in a special way.
  • Ensuring that the receiver's proof of cheating can only come from the evaluation circuits and not check circuits (since checking a circuit allows the receiver to learn all output wire labels). This is done by performing the secondary protocol before the check circuits are checked.
  • Ensuring that the secondary 2PC computation is small. With careful analysis, it is shown how to garble the circuit underlying the secondary computation using only ⚠ {$\ell$} AND-gates, where ⚠ {$\ell$} is the output length of the primary computation.

Other links:

CRYPTO presentation (video)

Categories:

CutAndChoose