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)$.Category / Keywords: cryptographic protocols / Secure Computation; Cut-and-Choose, LEGO, XOR-Homomorphic Hash Date: received 26 Oct 2015, last revised 3 Nov 2015 Contact author: yh33 at indiana edu Available format(s): PDF | BibTeX Citation Version: 20151104:020938 (All versions of this report) Short URL: ia.cr/2015/1038 Discussion forum: Show discussion | Start new discussion