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\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multiparty Homomorphic Secret Sharing and More from LPN and MQ

  • Geoffroy Couteau,
  • Naman Kumar,
  • Xiaxi Ye

摘要

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\) .