Paper 2017/150

Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation

Elette Boyle, Niv Gilboa, and Yuval Ishai


A recent work of Boyle et al. (Crypto 2016) suggests that ``group-based'' cryptographic protocols, namely ones that only rely on a cryptographically hard (Abelian) group, can be surprisingly powerful. In particular, they present succinct two-party protocols for securely computing branching programs and NC1 circuits under the DDH assumption, providing the first alternative to fully homomorphic encryption. 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.

Note: Preliminary full version

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2017
secure computationhomomorphic secret sharingshare conversionfully homomorphic encryption
Contact author(s)
eboyle @ alum mit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il
2017-07-07: revised
2017-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Niv Gilboa and Yuval Ishai},
      title = {Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/150},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.