Sublinear-Communication Secure Multiparty Computation does not require FHE

Elette Boyle; Geoffroy Couteau; Pierre Meyer

Paper 2023/1802

Sublinear-Communication Secure Multiparty Computation does not require FHE

Elette Boyle, Reichman University, NTT Research

Geoffroy Couteau, Université Paris Cité, CNRS, IRIF

Pierre Meyer, Reichman University, Université Paris Cité, CNRS, IRIF

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 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). This remains the state of affairs even for just three parties, with two corruptions. 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2023
DOI: https://doi.org/10.1007/978-3-031-30617-4_6
Keywords: Foundations Secure Multiparty Computation Function Secret Sharing Private Information Retrieval
Contact author(s): eboyle @ alum mit edu
couteau @ irif fr
pierre meyer @ irif fr
History: 2023-11-24: approved; 2023-11-22: received; See all versions
Short URL: https://ia.cr/2023/1802
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1802,
      author = {Elette Boyle and Geoffroy Couteau and Pierre Meyer},
      title = {Sublinear-Communication Secure Multiparty Computation does not require {FHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1802},
      year = {2023},
      doi = {https://doi.org/10.1007/978-3-031-30617-4_6},
      url = {https://eprint.iacr.org/2023/1802}
}