Cryptology ePrint Archive: Report 2016/1069

Constant Round Maliciously Secure 2PC with Function-independent Preprocessing using LEGO

Jesper Buus Nielsen and Thomas Schneider and Roberto Trifiletti

Abstract: Secure two-party computation (S2PC) allows two parties to compute a function on their joint inputs while leaking only the output of the function. At TCC 2009 Orlandi and Nielsen proposed the LEGO protocol for maliciously secure 2PC based on cut-and-choose of Yao's garbled circuits at the gate level and showed that this is asymptotically more efficient than on the circuit level. Since then the LEGO approach has been improved upon in several theoretical works, but never implemented. In this paper we describe further concrete improvements and provide the first implementation of a protocol from the LEGO family. Our protocol is optimized for the offline/online setting and supports function-independent preprocessing using only a constant number of rounds. We have benchmarked our prototype and find that our protocol can compete with all existing implementations and that it is often more efficient. As an example, in a LAN setting we can evaluate an AES-128 with online latency down to 1.13 ms, while if evaluating 128 AES-128 in parallel the amortized cost is 0.09 ms per AES-128. This online performance does not come at the price of offline inefficiency as we achieve comparable performance to previous, less general protocols, and significantly better if we ignore the cost of the function-independent preprocessing. Also, as our protocol has an optimal 2-round online phase it is significantly more efficient than previous protocols' when considering a high latency network.

Category / Keywords: implementation / Secure Two-party Computation, Implementation, LEGO, XOR-Homomorphic Commitments, Selective OT-Attack

Original Publication (in the same form): The Network and Distributed System Security Symposium (NDSS) 2017

Date: received 15 Nov 2016, last revised 9 Dec 2016

Contact author: roberto at cs au dk

Available format(s): PDF | BibTeX Citation

Note: Minor changes and typo fixes throughout the paper

Version: 20161209:145312 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]