Tomorrow, November 13, Dr. Hemanta Maji will be taking part in a colloquium. There will be a reception from 3:30 to 4:00 p.m. in 348 Avery Hall followed by the talk from 4:00 to 5:00 p.m. in 115 Avery Hall.
The subject of the colloquium will be "Secure Computation Over Leaky Channels."
An oblivious transfer (OT) channel takes as input a pair of bits (s[0],s[1]) from the sender and delivers (c,s[c]) to the receiver, where c is a uniform random bit. A secure implementation of such a channel hides c from the sender and the bit s[1-c] from the receiver. These secrecy properties make OT channels very useful for cryptography; for example, they can be used to perform general secure multi-party computation, cf. the work of Ishai, Prabhakaran and Sahai (CRYPTO 2008). Due to the high efficiency of information-theoretic techniques for secure computation using OT correlations, protocols such as TinyOT by Nielsen et al. (CRYPTO 2012) have popularized the approach in practice of starting with random bit OT correlations that is set up through an offline phase. But what if some information about the correlated randomness if leaked to an adversary? Can we still recover "fresh" correlated randomness after such leakage has happened? This question is a direct analog of the question of privacy amplification in the context of a shared random secret key, to 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 critical question of how much leakage is tolerable for preserving OT correlations has remained open. 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. Since then, no progress has been made on this question. In our work, we show that starting with n random bit OT correlations, where each party holds 2n bits, up to n/2 bits of leakage are tolerable. This result is optimal, by our complementary negative results. 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 we call the inner product correlation) where each party receives 2n bits, and up to n bits of leakage are tolerable.
Hemanta Maji is a post-doctoral researcher and a Center Fellow at the Center for Encrypted Functionalities in University of California, Los Angeles.