### Constant-Overhead Unconditionally Secure Multiparty Computation over Binary Fields

Antigoni Polychroniadou and Yifan Song

##### 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.

##### Metadata
Available format(s)
Category
Applications
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
Multiparty ComputationInformation-theoretic CryptographyCommunication Complexity
Contact author(s)
antigonipoly @ gmail com
yifans2 @ andrew cmu edu
History
2021-03-04: revised
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1412
License

CC BY

BibTeX

@misc{cryptoeprint:2020/1412,
author = {Antigoni Polychroniadou and Yifan Song},
title = {Constant-Overhead Unconditionally Secure Multiparty Computation over Binary Fields},
howpublished = {Cryptology ePrint Archive, Paper 2020/1412},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1412}},
url = {https://eprint.iacr.org/2020/1412}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.