A fundamental concept in cryptography is pseudorandomness, namely the ability to efficiently generate many bits that look indistinguishable from random. For example, if two parties can agree on a short random seed, a pseudorandom generator allows them to later obtain long random strings that look essentially uniform.
Motivated by concerns in secure multiparty computation, a recent generalization of this primitive has been designed and studied. Namely, from two short correlated seeds, long correlated strings can be generated later, without requiring any further communication from the parties. Such objects, termed pseudorandom correlation generators (PCGs), result in some of the most efficient secure computation protocols.
In this presentation, we will first discuss a general recipe for PCGs, studying the important special case of the oblivious transfer (OT) correlation. We will observe that a crucial ingredient is a pseudorandom generator that has sufficient linear structure; i.e., a pseudorandom generator derived from a “learning parity with noise”-type assumption. In the second half of the talk, we will discuss new coding-theoretic assumptions which have been proposed to design highly-efficient PCGs. As a particular highlight, we will discuss a PCG requiring only linear time to expand short seeds into many OT instances.
Based on joint works with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Peter Scholl.
Lisa Kohl is a senior researcher with the CWI Cryptology Group in Amsterdam. A special focus of her research work lies in exploring new directions for secure computation, with the goal of developing practical post-quantum secure protocols. Website: lisakohl.me
Nicolas Resch is an assistant professor with the Theoretical Computer Science Group from the Informatics Institute of the University of Amsterdam. His research focusses on error-correcting codes and cryptography and (naturally) their intersection. Website: nicolas-resch.caard.co