International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Sublinear-Communication Secure Multiparty Computation does not require FHE

Authors:
Elette Boyle , Reichman University and NTT Research
Geoffroy Couteau , Université Paris Cité, IRIF, CNRS
Pierre Meyer , Reichman University and Université Paris Cité, IRIF, CNRS
Download:
DOI: 10.1007/978-3-031-30617-4_6 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be *sublinear* in the circuit representation size of the desired function. Significant advances have been made affirmatively answering this question within the {\em two-party} setting, based on a variety of structures and hardness assumptions. In contrast, in the *multi-party* setting, only one general approach is known: using Fully Homomorphic Encryption (FHE). We present a framework for achieving secure sublinear-communication $(N+1)$-party computation, building from a particular form of Function Secret Sharing for only $N$ parties. In turn, we demonstrate implications to sublinear secure computation for various function classes in the 3-party and 5-party settings based on an assortment of assumptions not known to imply FHE.
BibTeX
@inproceedings{eurocrypt-2023-32933,
  title={Sublinear-Communication Secure Multiparty Computation does not require FHE},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30617-4_6},
  author={Elette Boyle and Geoffroy Couteau and Pierre Meyer},
  year=2023
}