International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration

Authors:
Shweta Agrawal , Indian Institute of Technology Madras, India
Yuval Ishai , Technion, Israel
Eyal Kushilevitz , Technion, Israel
Varun Narayanan , Tata Institute of Fundamental Research, Mumbai, India
Manoj Prabhakaran , Indian Institute of Technology Bombay, India
Vinod M. Prabhakaran , Tata Institute of Fundamental Research, Mumbai, India
Alon Rosen , IDC Herzliya, Israel
Download:
DOI: 10.1007/978-3-030-84245-1_5 (login may be required)
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: Can a sender encode a pair of messages (m_0,m_1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one? Garg et al. (Crypto 2015) showed that this is information-theoretically impossible. We show how to circumvent this impossibility by assuming that the receiver is computationally bounded, settling for an inverse-polynomial security error (which is provably necessary), and relying on ideal obfuscation. Our solution creates a ``computational anti-correlation'' between the events of receiving m_0 and receiving m_1 by exploiting the anti-concentration of the binomial distribution. The ideal obfuscation primitive in our construction can either be directly realized using (stateless) tamper-proof hardware, yielding an unconditional result, or heuristically instantiated using existing indistinguishability obfuscation schemes. We put forward a new notion of obfuscation that suffices to securely instantiate our construction. As a corollary, we get similar feasibility results for general secure computation of sender-receiver functionalities by leveraging the completeness of the above ``random oblivious transfer'' functionality.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31197,
  title={Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84245-1_5},
  author={Shweta Agrawal and Yuval Ishai and Eyal Kushilevitz and Varun Narayanan and Manoj Prabhakaran and Vinod M. Prabhakaran and Alon Rosen},
  year=2021
}