Secure Computation from Leaky Correlated Randomness

Correlated secret randomness is an essential resource for information-theoretic cryptography. In the context of secure two-party computation, the high level of efficiency achieved by information-theoretic protocols has motivated a paradigm of starting with correlated randomness, specifically random oblivious transfer (OT) correlations. This correlated randomness can be generated and stored during an offline preprocessing phase, long before the inputs are known. But what if some information about the correlated randomness is leaked to an adversary or to the other party? Can we still recover “fresh” correlated randomness after such leakage has occurred?

This question is a direct analog of the classical question of privacy amplification, which addresses the case of a shared random secret key, in the setting of correlated random secrets. Remarkably, despite decades of study of OT-based secure computation, very little is known about this question. In particular, the question of how much leakage is tolerable when recovering OT correlations has remained wide open. In our work, we resolve this question.

Prior to our work, the work of Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS 2009) obtained an initial feasibility result, tolerating only a tiny constant leakage rate. In our work, we show that starting with n random OT correlations, where each party holds 2n bits, up to (1-\eps)n/2 bits of leakage are tolerable. This result is optimal, by known negative results on OT combiners.

We then ask the same question for other correlations: is there a correlation that is more leakage-resilient than OT correlations, and also supports secure computation? We answer in the affirmative, by showing that there exists a correlation that can tolerate up to 1/2-\eps fractional leakage, for any \eps>0 (compared to the optimal 1/4 fractional leakage for OT correlations).