Welcome to the resource topic for 2021/943
Title:
Breaking the Circuit-Size Barrier for Secure Computation under Quasi-Polynomial LPN
Authors: Geoffroy Couteau, Pierre Meyer
Abstract:In this work we introduce a new (circuit-dependent) homomorphic secret sharing (HSS) scheme for any \log/\log\log-local circuit, with communication proportional only to the width of the circuit and polynomial computation, which is secure assuming the super-polynomial hardness of learning parity with noise (LPN). At the heart of our new construction is a pseudorandom correlation generator (PCG) which allows two parties to locally stretch short seeds into pseudorandom instances of an arbitrary \log/\log\log-local additive correlation. Our main application, and the motivation behind this work, is a generic two-party secure computation protocol for every layered (boolean or arithmetic) circuit of size s with total communication O(s/\log\log s) and polynomial computation, assuming the super-polynomial hardness of the standard learning parity with noise assumption (a circuit is layered if its nodes can be partitioned in layers, such that any wire connects adjacent layers). This expands the set of assumptions under which the `circuit-size barrier’ can be broken, for a large class of circuits. The strength of the underlying assumption is tied to the sublinearity factor: we achieve communication O(s/k(s)) under the s^{2^{k(s)}}-hardness of LPN, for any k(s) \leq (\log\log s) / 4. Previously, the set of assumptions known to imply a PCG for correlations of degree \omega(1) or generic secure computation protocols with sublinear communication was restricted to LWE, DDH, and a circularly secure variant of DCR.
ePrint: https://eprint.iacr.org/2021/943
Talk: https://www.youtube.com/watch?v=LMqkRnE9BFM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .