Paper 2023/650

Pseudorandom Correlation Functions from Variable-Density LPN, Revisited

Geoffroy Couteau, French National Centre for Scientific Research, IRIF, Université Paris-Cité
Clément Ducros, Université Paris-Cité, IRIF, Inria Saclay - Île-de-France Research Centre

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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2023
Correlated RandomnessPseudorandom Correlation FunctionsLearning parity with noiseWeak pseudorandom functions
Contact author(s)
couteau @ irif fr
cducros @ irif fr
2023-05-11: approved
2023-05-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Geoffroy Couteau and Clément Ducros},
      title = {Pseudorandom Correlation Functions from Variable-Density LPN, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2023/650},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.