Multiparty Homomorphic Secret Sharing and More from LPN and MQ
摘要
We give the first constructions of multiparty pseudorandom correlation generators, distributed point functions, and (negligible-error) homomorphic secret sharing for constant-degree polynomials for any number of parties without using LWE or iO. Our constructions are proven secure under the combination of LPN with dimension n, 2n samples, and noise rate \(n^{\varepsilon -1}\) for a small constant \(\varepsilon \) , and MQ with n variables and \(n^{1+\delta }\) equations. As applications of our results, we obtain from the same assumptions secure multiparty computation protocols with sublinear communication and silent preprocessing, as well as private information retrieval for M servers and size- \(\lambda ^d\) databases with optimal download rate and client-to-server communication \(M^d\cdot \lambda ^3\) .