Elette Boyle

STOC Conference 2024 Conference Paper

Memory Checking Requires Logarithmic Overhead

• Elette Boyle
• Ilan Komargodski
• Neekon Vafa

FOCS Conference 2020 Conference Paper

Correlated Pseudorandom Functions from Variable-Density LPN

• Elette Boyle
• Geoffroy Couteau
• Niv Gilboa
• Yuval Ishai
• Lisa Kohl
• Peter Scholl

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 ( $k_{0}, k_{1}$ ), the outputs $(f_{k_{0}}(x), f_{k_{1}}(x))$ are indistinguishable from 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 $\text{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) $\text{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.

STOC Conference 2012 Conference Paper

Multiparty computation secure against continual memory leakage

• Elette Boyle
• Shafi Goldwasser
• Abhishek Jain 0002
• Yael Tauman Kalai

We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental. Our result relies on standard cryptographic assumptions, and our security parameter is polynomially related to the number of parties.