International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Quang Dao , Carnegie Mellon University
Yuval Ishai , Technion
Aayush Jain , Carnegie Mellon University
Huijia Lin , University of Washington
Download:
DOI: 10.1007/978-3-031-38545-2_11 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Over the past few years, we have seen the powerful emergence of homomorphic secret sharing (HSS) as a compelling alternative to fully homomorphic encryption (FHE), due to its efficiency benefits and its feasibility from an array of standard assumptions. However, all previously known HSS schemes, with the exception of schemes built from FHE or indistinguishability obfuscation (iO), can only support two parties. In this work, we give the first construction of a \emph{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 \emph{arbitrary} number of parties with an \emph{arbitrary} corruption threshold, supporting evaluations of log⁡/log⁡log-degree polynomials, containing a polynomial number of monomials, over arbitrary finite fields. As a consequence, we obtain an MPC protocol for any number of parties, with (slightly) \emph{sub-linear} communication per party of roughly O(S/log⁡log⁡S) bits when evaluating a layered Boolean circuit of size S. Our HSS scheme relies on the \emph{sparse} Learning Parity with Noise (LPN) 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 \emph{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.
BibTeX
@inproceedings{crypto-2023-33220,
  title={Multi-Party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38545-2_11},
  author={Quang Dao and Yuval Ishai and Aayush Jain and Huijia Lin},
  year=2023
}