Study group: Crytography with One-Way Communication

The study group this week was on the paper "Cryptography withOne-Way Communication" by Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

In this paper the authors start the study of secure computation over noisy channel in the one-way setting, where only one party speaks. Different types of discrete noisy channels are considered and relationships  among them are studied (see the picture below).

It turns out that in the one-way setting the Binary Erasure Channel (BEC) and the Binary Symmetric Channel (BSC), that are equivalent in the interactive setting, are qualitatively very different. In particular, it is proved that a BEC cannot be constructed given a BSC; moreover while the erasure probability  of a BEC can be arbitrarily manipulated, i.e. can be both increased and reduced, the probability of  correct transmission of a BSC can only be diminished.

It is well known that in the interactive setting, oblivious transfer (OT) can be realized in an unconditionally secure way from almost any discrete memoryless noisy channel (DMC). This is no longer true in the one-way setting. For example,  we can see what happens if we try to realize a ROT channel (where the sender inputs two bit-strings $m_0$ and $m_1$, and the receiver obtains either $m_0$ or $m_1$, both with probability 1/2) from a BEC non-interactively. For realizing a ROT channel, the sender encodes $m_0$ and $m_1$ into some bits, say x=$(x_1, \dots, x_k)$, and send them over a BEC; the receiver obtains some of  these bits,  say y=$(y_1, \dots, y_{k'})$, depending on the  noise of the channel,  and from y they  should be  able to recover only one input string.  Security of the receiver is guaranteed by the fact that the  output string only depends on the  randomness of the channel and not on the sender's choice. On the other hand security of the sender  implies that it is impossible for them to obtain both  $m_0$ and $m_1$  just using the received bits y. However using the fact in a BEC each bit is independently erased, the authors prove that this  happens with large enough probability, i.e. a receiver could be able to extract both $m_0$ and $m_1$. Roughly speaking, security of the sender permits to break security of the receiver.

This result is generalized to any Generalized Erasure Channel (GEC) and BSC, and also to the case of computational security.

However, ROT channel can be realized using other type of discrete channels, for example the perfect bursty channel. It is a special GEC where all the erased bits are contiguous (see the paper for more details).

In the second part of the paper the authors consider one-way secure computation protocols over noisy channels for deterministic and randomized functionalities. More in particular, they prove that both the BEC and BSC are sufficient for securely realizing any deterministic functionality in the one way setting. Roughly, they first notice that ZK suffices for realizing any deterministic functionality in the malicious setting, and then that is possible to realize ZK from GEC and BSC by just sending over the channel multiple independent instances of ZK-PCPs to amplify the soundness.

In  case of randomized functionalities neither the BEC nor BSC can be used.

It is however possible to realize any randomized functionalities from bursty channels (BC), using the reduction from BC to ROT and then using results from [IPS08] or [IKO+11]. While the result on deterministic functionalities permits to obtain the first (highly inefficient) truly non-interactive solution to the ZK problem, this latter result on randomized functionalities  offers a solution (again non-efficient)  to the problem of certification of cryptographic keys in the one-way setting.