CryptoDB
Breaking the Circuit Size Barrier for Secure Computation under Quasi-Polynomial LPN
| Authors: |
|
|---|---|
| Download: |
|
| 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
}