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.
No comments:
Post a Comment