We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions.
The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 $\mathsf{AC}^0[\oplus]$ that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) $\mathsf{AC}^0[\oplus]$ candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.
Category / Keywords: cryptographic protocols / correlated randomness, pseudorandom correlation functions, learning parity with noise, weak pseudorandom functions Original Publication (with major differences): FOCS 2020 Date: received 13 Nov 2020 Contact author: eboyle at alum mit edu,couteau@irif fr,niv gilboa@gmail com,yuvali@cs technion ac il,lisa kohl@cwi nl,peter scholl@cs au dk Available format(s): PDF | BibTeX Citation Version: 20201115:073914 (All versions of this report) Short URL: ia.cr/2020/1417