Correlated randomness is a ubiquitous resource in cryptography. A one-time pad, namely a pair of identical random keys, enables perfectly secure communication. More complex forms of correlated randomness can similarly facilitate protocols for secure multiparty computation that allow two or more parties to jointly compute a function of secret inputs revealing nothing beyond the output. An example for a useful correlation is oblivious transfer, where one party is given two random bits (s₀,s₁) and another party gets (b,s_b) for a random bit b.

In this work we initiate the study of correlated pseudorandom functions that offer the ability to generate an essentially unbounded amount of correlated pseudorandomness from short correlated keys using only local computation. We present efficient constructions of correlated pseudorandom functions for a broad class of useful correlations, including oblivious transfer, from a variable-density variant of the learning parity with noise assumption.

This is joint work with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai and Peter Scholl.