International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Breaking the Circuit Size Barrier for Secure Computation under Quasi-Polynomial LPN

Authors:
Geoffroy Couteau , CNRS, IRIF, Université de Paris, France
Pierre Meyer , École Normale Supérieure de Lyon and IDC Herzliya, Israel
Download:
DOI: 10.1007/978-3-030-77886-6_29 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: In this work we introduce a new (circuit-dependent) homomorphic secret sharing (HSS) scheme for all log/loglog-local circuits, with communication proportional only to the width of the circuit, and polynomial computation, 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 partie to locally stretch, from short seeds, pseudorandom instances of an arbitrary log / log log-local additive correlation. Our main application, and the main 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) ≤ log log s /4. Previously, the set of assumptions known to imply a PCG for correlations of degree ω(1) or generic secure computation protocols with sublinear communication was restricted to LWE, DDH, and a circularly secure variant of DCR.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30925,
  title={Breaking the Circuit Size Barrier for Secure Computation under Quasi-Polynomial LPN},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77886-6_29},
  author={Geoffroy Couteau and Pierre Meyer},
  year=2021
}