Cryptography from One-Way Communication: On Completeness of Finite Channels
Cryptography from One-Way Communication: On Completeness of Finite Channels
复制标题
单向通信的密码学：论有限通道的完备性
DOI：
10.1007/978-3-030-64840-4_22
复制
发表时间：
2020
影响因子：
3
通讯作者：
Alon Rosen
中科院分区：
文献类型：
--
作者：
Shweta Agrawal;Yuval Ishai;E. Kushilevitz;Varun Narayanan;M. Prabhakaran;V. Prabhakaran;Alon Rosen
Garg等人（Crypto 2015）在非交互式设置中发起了对噪声信道上的加密协议的研究，即当只有一方说话时。这项工作留下的一个主要问题是initechannels的完整性，其输入和输出字母表不会随着所需的安全级别而增长。在这项工作中，我们解决这个问题，通过获得以下结果：1.具有逆多项式误差的Bit-ROT的完备性。我们证明了bit-ROT（即，随机不经意传输信道，其中两个消息中的每一个是单个比特）可以用于实现具有逆多项式误差的一般随机化功能。2.没有有限通道是完全的且误差可忽略的作为对上述的补充，我们证明了没有有限通道可以用来实现具有可忽略误差的字符串ROT，这意味着在bit-ROT的完全性中的逆多项式误差是固有的。这甚至适用于半诚实的当事人和计算安全性，并与Garg等人所示的字符串ROT的（可忽略错误）完整性形成对比。3. Characterization of Finite Channels Enabled Zero-Knowledge Proofs.安全计算的一个重要实例是零知识证明。噪声信道可以潜在地用于实现真正的非交互式零知识证明，没有可信的公共随机性，并且具有在普通模型中无法实现的不可转移性和可否认性特征。Garg等人从二进制擦除信道（BEC）和二进制对称信道（BSC）中获得了这样的零知识证明。我们完成的图片显示，在事实上任何非平凡的渠道就足够了。
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 offinitechannels, 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:1.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.2.No Finite Channel is Complete with Negligible Error.To complement the above, we show thatnofinite 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.3.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 realizetruly non-interactivezero-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 factany non-trivial channelsuffices.
具有单向通信的密码学
DOI：
--
发表时间：
2015
期刊：
Lecture notes in computer science
影响因子：
--
作者：
Garg, Sanjam;Ishai, Yuval;Kushilevitz, Eyal;Ostrovsky, Rafail;Sahai, Amit
通讯作者：
Sahai, Amit