Secure Computation from One-Way Noisy Communication, or: Anti-correlation via Anti-concentration

Can a sender encode a pair of messages (m0, m1) 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 inversepolynomial security error (which is provably necessary), and relying on ideal obfuscation. Our solution creates a "computational anti-correlation" between the events of receiving m0 and receiving m1 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 in the plain model using existing indistinguishability obfuscation schemes.

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.