Blog written by Carsten Baum
In this blog post, I will write a little bit about Thomas Jakobsen’s talk “Faster Maliciously Secure Two-Party Computation Using the GPU”. For this blog post, I assume that the reader is familiar with Yao’s original Garbled Circuit (GC) protocol for secure two-party computation (2PC).
Thomas started with a description of techniques how to make GC protocols actively secure. The approach used in their paper was cut and choose, meaning that party A creates not one, but multiple garbled versions of the same circuit. About half of those garbled circuits will be chosen by the other party B to be completely opened up (to check that they were constructed correctly). If they were constructed correctly, then with a certain probability a certain number of the other circuits must be correct as well. This now introduces a number of other problems: (1) A might send inconsistent inputs of himself (2) A might send incorrect input wires for B. The authors deal with the second problem using an approach by [LP07], where the authors transform the input of B such that A learning a few bits of Bs new input does not reveal information about the actual input he had. To tackle problem (1), the authors use an approach by [sS13,FN13] which consists of computing an universal hash function on As inputs and B checking that these values are consistent for all circuits sent by A.
One could now evaluate all evaluation circuits and take the majority of the outputs. This yields a quite substantial overhead, but one can do better using the forge-and-lose technique due to [B13, HKE13, L13]: If one of the circuits does not evaluate to the same output value, then B can reconstruct the inputs of A (which makes him able to evaluate the computed circuit in the plain). As the main contribution of their work, the authors achieve this property without an additional MPC as in [L13] or trapdoor commitments as in [B13]. Instead, they use the free-XOR-optimization technique which reveals the input of A if ever two different output wires of the same gate are known to B. For every output gate, one can now construct a polynomial that goes through all the 0-wires and for the 1-wires respectively. By appropriately choosing the degree, this allows to compute all output values if at least one circuit is correct (which is true due to the cut and choose) and one is wrong. In the protocol, one now has to make sure that indeed all wires lie on a polynomial, but this was outside of the scope of Thomas’ talk.
He finally presented benchmark numbers for their implementation (which makes heavy use of an available GPU). According to the benchmark results, their work is superior to all preceding approaches in terms of runtime – even though potentially not comparable due to the use of the GPU and the fact that security only holds in the Random Oracle Model.