Paper 2023/1593
Multi-Party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN
Abstract
Over the past few years, homomorphic secret sharing (HSS) emerged as a compelling alternative to fully homomorphic encryption (FHE), due to its feasibility from an array of standard assumptions and its potential efficiency benefits. However, all known HSS schemes, with the exception of schemes built from FHE or indistinguishability obfuscation (iO), can only support two or four parties. In this work, we give the first construction of a multi-party HSS scheme for a non-trivial function class, from an assumption not known to imply FHE. In particular, we construct an HSS scheme for an arbitrary number of parties with an arbitrary corruption threshold, supporting evaluations of multivariate polynomials of degree $\log / \log \log$ over arbitrary finite fields. As a consequence, we obtain a secure multiparty computation (MPC) protocol for any number of parties, with (slightly) sub-linear per-party communication of roughly $O(S / \log \log S)$ bits when evaluating a layered Boolean circuit of size $S$. Our HSS scheme relies on the Sparse Learning Parity with Noise assumption, a standard variant of LPN with a sparse public matrix that has been studied and used in prior works. Thanks to this assumption, our construction enjoys several unique benefits. In particular, it can be built on top of any linear secret sharing scheme, producing noisy output shares that can be error-corrected by the decoder. This yields HSS for low-degree polynomials with optimal download rate. Unlike prior works, our scheme also has a low computation overhead in that the per-party computation of a constant degree polynomial takes $O(M)$ work, where $M$ is the number of monomials.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in CRYPTO 2023
- DOI
- 10.1007/978-3-031-38545-2_11
- Keywords
- homomorphic secret sharingHSSMPCsublinear MPCLPNsparse LPN
- Contact author(s)
-
qvd @ andrew cmu edu
yuvali @ cs technion ac il
aayushja @ andrew cmu edu
rachel @ cs washington edu - History
- 2023-10-17: approved
- 2023-10-14: received
- See all versions
- Short URL
- https://ia.cr/2023/1593
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1593, author = {Quang Dao and Yuval Ishai and Aayush Jain and Huijia Lin}, title = {Multi-Party Homomorphic Secret Sharing and Sublinear {MPC} from Sparse {LPN}}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1593}, year = {2023}, doi = {10.1007/978-3-031-38545-2_11}, url = {https://eprint.iacr.org/2023/1593} }