Geoffroy Couteau: Title: Correlated Pseudorandom Functions from Variable-Density LPN

Speaker: Geoffroy Couteau, CNRS research scientist at IRIF

Date: Friday, May 28, 2021

Time: 1:00 PM to 2:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: email dlehto@mit.edu for Zoom link

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan and Yael Kalai

Contact: Deborah Goodwin, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu, crypto@lists.csail.mit.edu

Reminder Subject: TALK: Geoffroy Couteau: Title: Correlated Pseudorandom Functions from Variable-Density LPN

Abstract: Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function F_k such that for a suitable joint key distribution (k0, k1), the outputs (F_k0(x), F_k1(x)) are indistinguishable from random instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys.

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 AC0[⊕] 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) AC0[⊕] 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.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2021.

Created by Deborah Goodwin at Monday, May 24, 2021 at 3:35 PM.