MPC Study Group: Cut-and-Choose

In this week’s zoom meetup we looked at the Cut-and-Choose technique [EKR17, §6.1-6.4]. We started the session by watching a video on fast cut-and-choose by Yehuda Lindell [Lindell13].

These are my personal study notes, so please refer to the references to verify any information in this post. The content of this post is mostly based on [EKR17].

Cut-and-Choose

The cut-and-choose protocol is used by the evaluator in garbled circuits to ensure that the garbled circuit is correct (remember, the circuit is generated by the “generator” party $P_1$, and evaluated by the “evaluator” party $P_2$). We start by describing the abstract cut-and-choose game to highlight its structure.

The Cut-and-Choose Game:

• Players $P_1$, $P_2$.
• $P_1$ generates $p$ balls with colours red or green.
• Checking:
  • $P_2$ chooses a random subset (size $c$) of balls for checking and checks them:
    • If any checked ball is red then $P_1$ loses.
• Evaluation:
  • $P_2$ evaluates the remaining balls.
  • If a majority of unchecked balls are red, then $P_1$ wins (alternative definition: if all of the unchecked balls are red).

In this abstract version, a red-coloured ball represents an incorrect garbled circuit, whereas a green ball represents a correct circuit. Using this protocol $P_2$ can catch $P_1$ cheating during the checking phase if any of the checked balls were incorrect. If this is the case, then $P_2$ can abort the protocol. If the check passes, then $P_2$ continues with the evaluation phase. If $P_1$ manages to pass the check and have a majority of red balls in the evaluation phase, then $P_1$ wins.

At this point we should reflect on the probability that $P_1$ wins. The optimal parameters for this protocol are: $p \approx 3.12 \lambda$, $c = 0.6 p$ (check the book for more info), for these parameters $P_1$ wins with probability $2^{-\lambda}$. Concretely, we might want to choose our $\lambda$ to be $40$, for which we need to choose $p \approx 120$ and $c = 72$ accordingly.

We can improve our parameters in a batched execution (over $N$ executions).

The Batched Cut-and-Choose Game:

• Players $P_1$, $P_2$.
• $P_1$ generates $N*p + c$ balls with colours red or green.
• Checking:
  • $P_2$ chooses a random subset (of size $c$) balls for checking and checks them:
    • If any checked ball is red, then $P_1$ loses.
• Evaluation:
  • $P_2$ assigns the remaining balls into $N$ buckets, each bucket containing $p$ balls.
  • $P_2$ evaluates the remaining buckets/balls.
  • If any bucket contains a majority of red balls, then $P_1$ wins (alternative definition: if any bucket contains only red balls).

The batched execution improves over the non-batched execution by performing fewer checks (amortized). The batched execution over $N$ execution performs only $c$ checks, whereas the non-batched execution repeated $N$ times performs $N*c$ checks. According to asymptotic analysis (check the book), we can set $p = 2 + \mathcal{O} (\lambda / log N)$ for probability $2^{-\lambda}$. We can give more concrete numbers, for security $2^{-40}$ and $N=1024$, $P_1$ generates 5593 balls, $473$ are checked, the remaining are evaluated: $p \approx 5$. As we have shown, performance benefit for the batched execution of cut-and-choose can be very large.

Cut-and-Choose on Garbled Circuits

We have now discussed how the cut-and-choose protocol works, but it may not be clear how it is applied to garbled circuits. As we will see, it can be applied in a straight-forward manner, but there are some things we still need to consider. We show how to do cut-and-choose for a single execution, but omit showing the batched cut-and-choose version as it should be clear how it can be extended.

The Cut-and-Choose for Garbled Circuits:

• Players $P_1$ the generator, $P_2$ the evaluator.
• Problem: ensure that the circuit is correct.
• $P_1$ generates independent $p$ garbled circuits.
• Checking:
  • $P_2$ chooses a random subset of circuits.
  • $P_2$ asks $P_1$ to open the chosen subset to reveal the randomness used to generate the circuits, and $P_2$ verifies that each opened circuit is correct.
    • If any circuit is incorrect, $P_2$ aborts.
• Evaluation:
  • $P_2$ evaluates all other non-checked circuits.
  • $P_2$ uses the majority value as output from circuits, send output to $P_1$.

Using this strategy $P_2$ can ensure that the circuit and output is correct with probability $1 - 2^{-\lambda}$. The cut-and-choose strategy, however, does not ensure that $P_1$ or $P_2$ use the same inputs for the circuits during the evaluation phase. $P_2$ can catch $P_1$ using different inputs (if the output of two circuits is not the same), but $P_1$ cannot catch $P_2$ using different inputs to the circuits. This can however be achieved through other means, in what we call input consistency checks.

$P_2$ input consistency:

• Problem: $P_1$ ensures that $P_2$’s inputs are consistent.
• During evaluation of cut-and-choose: perform the oblivious-transfer (OT) for each bit of $P_2$’s inputs together for all garbled circuits, such that an input-bit is chosen for all garbled circuits in a single 1-2 OT.

There are also strategies for ensuring that $P_1$’s inputs are consistent. If we do this, we can also perform the cut-and-choose alternative form that $P_1$ wins only if all unchecked balls are read, instead of a majority of unchecked balls. This is a further optimization.

$P_1$ input consistency:

• Problem: $P_2$ ensures that $P_1$’s inputs are consistent.
• The book discusses two strategies. One, in which $P_1$ commits to its inputs, and this commitment is checked in the secure function evaluation. Another technique is the one presented by Lindell [Lindell13], in which $P_1$ commits its inputs to an input recovery function, such that $P_2$ can recover $P_1$’s inputs if $P_2$ caught $P_1$ cheating. More details can be found in the book.

There are also further optimizations. One such optimization is to perform the batched cut-and-choose over garbled-gates (execution over garbled-gates), instead of over the garbled circuits (execution over garbled circuits). This way we can benefit from the reduced amortized cost using batching even if a function is evaluated once, as the batching is over the number of gates and not the number of function executions. The book [EKR17] covers these topics well, I recommend reading the referred sections and the mentioned references in the book.

References

• [EKR17] Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security. 2017 Jan;2(2-3).
• [Lindell13] Lindell, Y. 2013. “Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries”. In: Advances in Cryptology - CRYPTO 2013, Part II.Ed. by R. Canetti and J. A. Garay. Vol. 8043.Lecture Notes in Computer Science. Springer, Heidelberg. 1–17. doi: 10.1007/978-3-642-40084-1_1.