Truly Efficient $2$-Round Perfectly Secure Message Transmission Scheme
Truly Efficient $2$-Round Perfectly Secure Message Transmission Scheme
复制标题
DOI：
10.1109/tit.2009.2030434
复制
发表时间：
2008-04
影响因子：
2.5
通讯作者：
K. Kurosawa;Kazuhiro Suzuki
中科院分区：
文献类型：
--
作者：
K. Kurosawa;Kazuhiro Suzuki
在完全安全消息传输（PSMT）方案模型中，发送方和接收方之间有n个通道。无限强大的对手A可能破坏（观察和伪造）通过n个通道中的t发送的消息。发送方希望在不与接收方共享任何密钥的情况下，以完全私密和完全可靠的方式向接收方发送一个秘密。在本文中，我们展示了n = 2t + 1的第一个2轮PSMT，使得不仅传输速率为O(n)，而且发送方和接收方的计算成本都是n的多项式。这意味着我们解决了Agarwal， Cramer和de Haan在CRYPTO 2006上提出的开放问题。该方法的主要新颖之处在于在编码理论中引入了伪基的概念。它也将成为编码理论的一个独立兴趣。
In the model of perfectly secure message transmission (PSMT) schemes, there are n channels between a sender and a receiver. An infinitely powerful adversary A may corrupt (observe and forge) the messages sent through t out of n channels. The sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first 2-round PSMT for n = 2t + 1 such that not only the transmission rate is O(n) but also the computational costs of the sender and the receiver are both polynomial in n. This means that we solve the open problem raised by Agarwal, Cramer, and de Haan at CRYPTO 2006. The main novelty of our approach is to introduce a notion of pseudobasis to the coding theory. It will be an independent interest for coding theory, too.