MiniLEGO: Efficient Secure Two-Party Computation

MiniLEGO: Efficient Secure Two-Party Computation

Tore Kasper Frederiksen, Thomas Pelle Jakobsen, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi
EUROCRYPT 2013 [pdf] [bibtex]

In the LEGO paradigm of NO09?, a sender generates many garbled gates, a random half of which are opened and checked in a cut-and-choose phase. Later, the unopened gates are assembled into a fault tolerant circuit by a process called soldering. The result is a malicious-secure 2PC protocol, with an asymptotic efficiency improvement over traditional cut-and-choose that is logarithmic in the size of the circuit.

The original LEGO construction uses specific number-theoretic assumptions and uses public-key operations at each gate of the circuit. This paper improves on the original construction by basing the main LEGO paradigm on symmetric-key, standard-model assumptions only. In addition, the overall approach is streamlined and simplified.

The main technical ingredient is the construction of an XOR-homomorphic commitment scheme. The sender can commit to many values ⚠ {$x_1, x_2, \ldots$} and later reveal only the XOR of some of the values (e.g., reveal only ⚠ {$x_4 \oplus x_{11}$}).

The main idea of the commitment protocol is as follows: The parties use oblivious transfer so that the receiver picks up some secret set of bits (called the watch bits) from a random codeword in a suitable linear code. The actual secret is masked by using the decoded codeword as a one-time pad. The receiver can decommit by revealing the mask/codeword, which the receiver will verify against the corresponding watch bits. Since the code is linear, commitments and openings can be XOR'ed in a natural way. Intuitively, the watch bits reveal no information about the decoded codeword, if there are few enough watch bits. On the other hand, the sender must change one codeword to another to successfully equivocate. If there are enough watch bits (relative to the code's minimum distance), the receiver is highly likely to detect this equivocation. Codes from algebraic geometry are suggested which achieve the appropriate balance of parameters.

The final protocol achieves a functionality slightly weaker than described above. The sender can in fact choose a very small set of values on which he can equivocate without detection. See the paper for details.

Given such a homomorphic commitment functionality, the LEGO paradigm can be achieved as follows (below we will assume familiarity with NO09?). The sender generates many garbled gates and commits to the "zero" wire label for each wire. A random subset of gates is opened and checked as usual, including the associated commitments. Later, to "solder" two wires together, the sender need only decommit to the XOR of their wire-labels. The resulting value is precisely what the receiver needs to XOR to a wire label to translate it from one wire to the other.

Importantly, since the underlying homomorphic operation on wire labels is XOR (rather than a cyclic group operation as in NO09?), the new approach is compatible with the free XOR optimization.

Categories:

CutAndChoose