Abstract
We initiate the study of "elastic noisy channels," where the reliability of the channel from the perspective of an honest user can be significantly worse than the reliability of the channel from the perspective of a malicious user. Such elastic channels naturally arise in situations where a malicious user can choose the antenna it uses to receive signals.
In the setting of elastic channels, we pose the following intriguing question: "Can we obliviously establish multiple channels between Sender and Receiver such that the highest capacity channel to an honest receiver has more capacity than the average capacity channel to the malicious receiver?'' We refer to this phenomenon in elastic noisy channels as: capacity inversion.
In this work, we consider elastic variants of classical noisy channels, namely the binary erasure channel and the binary symmetric channel. We identify non-interactive capacity inverting encodings, i.e. encodings which help achieve capacity inversion, for various parameters of these elastic noisy channels.
Leveraging capacity inversion, we efficiently found general unconditionally secure computation, over a large parameter space of elastic noisy channels. Prior techniques in secure computation only yield such solutions for a minuscule fraction of this space, for this more realistic model of noisy channels.
Joint work with Dakshita Khurana and Amit Sahai