International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 27 October 2015

Yan Huang, Ruiyu Zhu
ePrint Report ePrint Report
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)$.

Expand

Additional news items may be found on the IACR news page.