International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptography from One-Way Communication: On Completeness of Finite Channels

Shweta Agrawal
Yuval Ishai
Eyal Kushilevitz
Varun Narayanan
Manoj Prabhakaran
Vinod Prabhakaran
Alon Rosen
DOI: 10.1007/978-3-030-64840-4_22
Search ePrint
Search Google
Abstract: Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of {\em finite} channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results: Completeness of Bit-ROT with Inverse Polynomial Error: We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error. No Finite Channel is Complete with Negligible Error: To complement the above, we show that {\it no} finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al. Characterization of Finite Channels Enabling Zero-Knowledge Proofs: An important instance of secure computation is zero-knowledge proofs. Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.
Video from ASIACRYPT 2020
  title={Cryptography from One-Way Communication: On Completeness of Finite Channels},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Shweta Agrawal and Yuval Ishai and Eyal Kushilevitz and Varun Narayanan and Manoj Prabhakaran and Vinod Prabhakaran and Alon Rosen},