International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Constant-Overhead Unconditionally Secure Multiparty Computation over Binary Fields

Authors:
Yifan Song , CMU
Antigoni Polychroniadou , J.P. Morgan AI Research
Download:
DOI: 10.1007/978-3-030-77886-6_28 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: We study the communication complexity of unconditionally secure multiparty computation (MPC) protocols in the honest majority setting. Despite tremendous efforts in achieving efficient protocols for binary fields under computational assumptions, there are no efficient unconditional MPC protocols in this setting. In particular, there are no n party protocols with constant overhead admitting communication complexity of O(n) bits per gate. Cascudo, Cramer, Xing and Yuan (CRYPTO 2018) were the first ones to achieve such an overhead in the amortized setting by evaluating O(log n) copies of the same circuit in the binary field in parallel. In this work, we construct the first unconditional MPC protocol secure against a malicious adversary in the honest majority setting evaluating just a single boolean circuit with amortized communication complexity of O(n) bits per gate.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30899,
  title={Constant-Overhead Unconditionally Secure Multiparty Computation over Binary Fields},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77886-6_28},
  author={Yifan Song and Antigoni Polychroniadou},
  year=2021
}