## Founding cryptography on oblivious transfer – efficiently.(English)Zbl 1183.94037

Wagner, David (ed.), Advances in cryptology – CRYPTO 2008. 28th annual international cryptology conference, Santa Barbara, CA, USA, August 17–21, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85173-8/pbk). Lecture Notes in Computer Science 5157, 572-591 (2008).
Summary: 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) + \text{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).
For the entire collection see [Zbl 1155.94010].

### MSC:

 94A60 Cryptography 68M12 Network protocols 68M14 Distributed systems 94A62 Authentication, digital signatures and secret sharing
Full Text: