In this work we further explore the power of group-based secure computation protocols, improving both their asymptotic and concrete efficiency. We obtain the following results.
- Black-box use of group. We modify the succinct protocols of Boyle et al. so that they only make a black-box use of the underlying group, eliminating an expensive non-black-box setup phase. - Round complexity. For any constant number of parties, we obtain 2-round MPC protocols based on a PKI setup under the DDH assumption. Prior to our work, such protocols were only known using fully homomorphic encryption or indistinguishability obfuscation. - Communication complexity. Under DDH, we present a secure 2-party protocol for any NC1 or log-space computation with n input bits and m output bits using n+(1+o(1)) m+\poly(\lambda) bits of communication, where \lambda is a security parameter. In particular, our protocol can generate n instances of bit-oblivious-transfer using (4+o(1))\cdot n bits of communication. This gives the first constant-rate OT protocol under DDH. - Computation complexity. We present several techniques for improving the computational cost of the share conversion procedure of Boyle et al., improving the concrete efficiency of group-based protocols by several orders of magnitude.
Category / Keywords: secure computation, homomorphic secret sharing, share conversion, fully homomorphic encryption Original Publication (in the same form): IACR-EUROCRYPT-2017 Date: received 16 Feb 2017, last revised 7 Jul 2017 Contact author: eboyle at alum mit edu, gilboan@bgu ac il, yuvali@cs technion ac il Available format(s): PDF | BibTeX Citation Note: Preliminary full version Version: 20170707:114456 (All versions of this report) Short URL: ia.cr/2017/150 Discussion forum: Show discussion | Start new discussion