Paper 2023/1593

Multi-Party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN

Quang Dao, Carnegie Mellon University
Yuval Ishai, Technion – Israel Institute of Technology
Aayush Jain, Carnegie Mellon University
Huijia Lin, University of Washington
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.