Paper 2023/1593 Original: eprint.iacr.org/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.