Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme

Kaoru Kurosawa; Kazuhiro Suzuki

Paper 2008/421

Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme

Kaoru Kurosawa and Kazuhiro Suzuki

Abstract

In the model of perfectly secure message transmission schemes (PSMTs), 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 = 2 t + 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 . This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006.

Note: Sec.2.2 and Sec.2.3 are revised.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. This is a revised version of Eurocrypt 2008.
Keywords: perfectly secure message transmission information theoretic security
Contact author(s): kurosawa @ mx ibaraki ac jp
History: 2008-12-05: revised; 2008-10-02: received; See all versions
Short URL: https://ia.cr/2008/421
License: CC BY

BibTeX

@misc{cryptoeprint:2008/421,
      author = {Kaoru Kurosawa and Kazuhiro Suzuki},
      title = {Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/421},
      year = {2008},
      url = {https://eprint.iacr.org/2008/421}
}