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 effi-
ciency. 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(λ) bits of communication,
where λ is a security parameter. In particular, our protocol
can generate n instances of bit-oblivious-transfer using (4 + o(1)) · 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.