Non-Interactive Secure Computation Based on Cut-and-Choose

A talk by Arash Afshar (joint work with Payman Mohassel, Benny Pinkas and Ben Riva).

Arash explains how to do non-interactive, maliciously secure two-party computation, with efficiency comparable to the most efficient secure two-party computation protocols. In the context of the talk non-interactivity means that only two messages are sent in the entire protocol. One from Alice to Bob and then one from Bob to Alice. A motivation for looking into non-interactively is first of all the fact that latency in communication networks gives unavoidable increase in execution time so we want to limit the amount of rounds, but also the fact that with non-interactivity we can do asynchronous execution of secure computation.

The approach that Arash and his co-authors use to achieve non-interactive secure computation (NISC) is cut-and-choose of garbled circuits. This is an approach which has received much work both in its theoretical, but also in its practical aspects, in the recent years. Unfortunately cut-and-choose is inherently an interactive paradigm as it requires one party to sent a bunch of candidate values (in this case garbled circuits), then the other party randomly selects a subset of these candidates for verification, which means that the sending party sends all the information and randomness used in constructing these candidates to the receiving party. If all the candidates selected for verification were correctly constructed the receiving party knows that with large probability a lot of the remaining candidates are correctly constructed. Arash and his co-authors overcome this interactivity problem by embedding the choice of check and evaluation candidates into some non-interactive oblivious transfers (OT).

Unfortunately, when doing cut-and-choose of garbled circuits some issues arise, such as the problem with selective failure and input consistency. In general both of these can be handled with off the shelf constructions. However, these are not in general non-interactive. Still, for the selective failure problem a non-interactive solution exist which is called committing OT. This is also the solution Arash and his co-authors use in their protocol. For the problem of input consistency they introduce a new gadget which is an equality prover that gives the receiving party a proof that the sending party has given the same input to each of the garbled circuits.

To make their construction more competitive Arash and his co-authors also implement a non-interactive version of a recent optimization, making it possible to successfully execute the entire protocol even though only one correct evaluation circuit remains after cut-and-choose. In general it is needed that a majority of correct circuits remain for evaluation. In this optimization if the sending party constructs a circuit incorrectly which is evaluated, then the sending party's input is leaked making it possible for the party evaluating the circuits to compute the output in plain. Arash explains that they achieve this by changing the input keys to trapdoor ElGamal commitments such that knowing both a 0 and a 1 key on a given output wire leaks a trapdoor to the commitments on the input keys, making it possible for the evaluator to learn the input of the sending party.

Finally, Arash and his co-authors also introduce the first implementation of any NICS protocol. Their implementation runs on a common laptop through a Linux VM and uses the AES-NI instruction extension for the garbling, but only runs a single thread and uses disc IO to simulate communication between the parties. Assuming decent security parameters their implementation runs oblivious AES in 6.4 seconds. From their implementation they see that the time spent on garbling and cheating recovery is very small and that the bottlenecks are the exponentiations needed for the commitments and the communication (which in this case is IO).