| Event Details |
|---|
|
Thursday, November 13, 2014 Talk:
4:00 p.m., Avery 115
Reception:
3:30 p.m., Avery 348
|
Dr. Hemanta Maji
Post-Doctoral Researcher, University of California, Los AngelesAbstract
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.
Additional Info: This talk is based on joint works with Divya Gupta, Yuval Ishai, Amit Sahai and Jurg Wullschleger. In several ongoing works, we are exploring the conjectures and the open problems mentioned in this talk.
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.
Additional Info: This talk is based on joint works with Divya Gupta, Yuval Ishai, Amit Sahai and Jurg Wullschleger. In several ongoing works, we are exploring the conjectures and the open problems mentioned in this talk.
Speaker Bio
Hemanta Maji is a post-doctoral researcher and a Center Fellow at the Center for Encrypted Functionalities in University of California, Los Angeles. He was a Computing Innovations Fellow sponsored by Computing Research Association from 2011 to 2013.
He obtained his Ph.D. in computer science from University of Illinois, Urbana-Champaign and his undergraduate B.Tech. from Indian Institute of Technology, Kanpur. His research interest is cryptography, in general, and secure computation, in particular. He has over 15 original peer reviewed publications at venues like FOCS, CRYPTO, EUROCRYPT and Innovations in Computer Science. His current research focusses on developing highly efficient protocols which strong mathematical security guarantees.
He obtained his Ph.D. in computer science from University of Illinois, Urbana-Champaign and his undergraduate B.Tech. from Indian Institute of Technology, Kanpur. His research interest is cryptography, in general, and secure computation, in particular. He has over 15 original peer reviewed publications at venues like FOCS, CRYPTO, EUROCRYPT and Innovations in Computer Science. His current research focusses on developing highly efficient protocols which strong mathematical security guarantees.