Welcome to the resource topic for 2023/650
Title:
Pseudorandom Correlation Functions from Variable-Density LPN, Revisited
Authors: Geoffroy Couteau, Clément Ducros
Abstract:Pseudorandom correlation functions (PCF), introduced in
the work of (Boyle et al., FOCS 2020), allow two parties to locally gen-
erate, from short correlated keys, a near-unbounded amount of pseu-
dorandom samples from a target correlation. PCF is an extremely ap-
pealing primitive in secure computation, where they allow to confine
all preprocessing phases of all future computations two parties could
want to execute to a single short interaction with low communication
and computation, followed solely by offline computations. Beyond in-
troducing the notion, Boyle et al. gave a candidate construction, using
a new variable-density variant of the learning parity with noise (LPN)
assumption. Then, to provide support for this new assumption, the au-
thors showed that it provably resists a large class of linear attacks, which
captures in particular all known attacks on LPN.
In this work, we revisit the analysis of the VDLPN assumption. We make
two key contributions:
– First, we observe that the analysis of Boyle et al is purely asymp-
totic: they do not lead to any concrete and efficient PCF instanti-
ation within the bounds that offer security guarantees. To improve
this state of affairs, we combine a new variant of a VDLPN assump-
tion with an entirely new, much tighter security analysis, which we
further tighten using extensive computer simulations to optimize pa-
rameters. This way, we manage to obtain for the first time a set of
provable usable parameters (under a simple combinatorial conjec-
ture which is easy to verify experimentally), leading to a concretely
efficient PCF resisting all linear tests.
– Second, we identify a flaw in the security analysis of Boyle et al.,
which invalidates their proof that VDLPN resists linear attacks. Us-
ing several new non-trivial arguments, we repair the proof and fully
demonstrate that VDLPN resists linear attack; our new analysis is
more involved than the original (flawed) analysis.
Our parameters set leads to PCFs with keys around 3MB allowing ∼
500 evaluations per second on one core of a standard laptop for 110
bits of security; these numbers can be improved to 350kB keys and ∼
3950 evaluations/s using a more aggressive all-prefix variant. All numbers
are quite tight: only within a factor 3 of the best bounds one could
heuristically hope for.
ePrint: https://eprint.iacr.org/2023/650
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 .