Paper 2023/1802
Sublinear-Communication Secure Multiparty Computation does not require FHE
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
- FoundationsSecure Multiparty ComputationFunction Secret SharingPrivate 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},
note = {\url{https://eprint.iacr.org/2023/1802}},
url = {https://eprint.iacr.org/2023/1802}
}
