Paper 2015/1038

Revisiting LEGOs: Optimizations, Analysis, and their Limit

Yan Huang and Ruiyu Zhu

Abstract

The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario. Nielsen and Orlandi et al. have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., LEGO is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while MiniLEGO leaves the important building-block of soldering unspecified. In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implementation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to “a majority of”) correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a “bad” gate being detected in the check stage (compared to MiniLEGO). Our construction is more bandwidth-efficient than Lindell (CRYPTO, 2013) either when the circuit size N is sufficiently large, or when N is larger than a threshold solely determined by the ratio between the input and circuit sizes. E.g., we use less bandwidth for computing most linear and sub-linear functions. Deploying a LEGO-style cut-and-choose protocol involves convoluted protocol parameter selection. To this end, we give a thorough analysis of the relations among all protocol parameters and propose efficient algorithms that automate the search for the optimal parameter configuration based on a requirement specification (i.e., the security parameters s,k and application parameter N) with provable accuracy. Last, we formally prove a tight bound on the benefit of LEGO-style secure computation protocols, in the sense that the circuit duplication factor $\kappa$ has to be larger than 2 and any $\kappa > 2$ is indeed achievable. This corrects a common mistake of claiming LEGO cut-and-choose can reduce $\kappa$ to $O(sk/ \log N)$ since $2 \not\in O(sk/\log N)$.