Founding Cryptography on Oblivious Transfer – Efficiently

We present a simple and efficient compiler for transforming secure multi-party computation (MPC) protocols that enjoy security only with an honest majority into MPC protocols that guarantee security with no honest majority, in the oblivious-transfer (OT) hybrid model. Our technique works by combining a secure protocol in the honest majority setting with a protocol achieving only security against

semi-honest

parties in the setting of no honest majority.

Applying our compiler to variants of protocols from the literature, we get several applications for secure two-party computation and for MPC with no honest majority. These include:

Constant-rate two-party computation in the OT-hybrid model.

We obtain a statistically UC-secure two-party protocol in the OT-hybrid model that can evaluate a general circuit

C

of size

s

and depth

d

with a total communication complexity of

O

(

s

) + 

poly

(

k

,

d

, log

s

) and

O

(

d

) rounds. The above result generalizes to a constant number of parties.

Extending OTs in the malicious model.

We obtain a computationally efficient protocol for generating many string OTs from few string OTs with only a

constant amortized communication overhead

compared to the total length of the string OTs.

Black-box constructions for constant-round MPC with no honest majority.

We obtain general computationally UC-secure MPC protocols in the OT-hybrid model that use only a constant number of rounds, and only make a

black-box

access to a pseudorandom generator. This gives the first constant-round protocols for three or more parties that only make a black-box use of cryptographic primitives (and avoid expensive zero-knowledge proofs).