In collaboration with IDC Herzliya + Technion and UCLA
Elette Boyle, Niv Gilboa and Yuval Ishai
Advances in Cryptology – EUROCRYPT 2017, pages 163-193, 2017
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 computingbranching 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 computationprotocols, improving both their asymptotic and concrete effi-ciency. We obtain the following results.– Black-box use of group. We modify the succinct protocols of Boyleet 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 obtain2-round MPC protocols based on a PKI setup under the DDH assumption.Prior to our work, such protocols were only known using fullyhomomorphic 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 bitsand m output bits using n + (1 + o(1))m + poly(λ) bits of communication,where λ is a security parameter. In particular, our protocolcan generate n instances of bit-oblivious-transfer using (4 + o(1)) · nbits of communication. This gives the first constant-rate OT protocolunder DDH.– Computation complexity. We present several techniques forimproving the computational cost of the share conversion procedure ofBoyle et al., improving the concrete efficiency of group-based protocolsby several orders of magnitude.