## CryptoDB

### Paper: 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 Search ePrint Search Google CRYPTO 2021 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.
##### BibTeX
@inproceedings{crypto-2021-31197,
title={Secure Computation from One-Way Noisy Communication, or: Anti-Correlation via Anti-Concentration},
publisher={Springer-Verlag},
author={Shweta Agrawal and Yuval Ishai and Eyal Kushilevitz and Varun Narayanan and Manoj Prabhakaran and Vinod M. Prabhakaran and Alon Rosen},
year=2021
}