International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme

Authors:
Kaoru Kurosawa
Kazuhiro Suzuki
Download:
URL: http://eprint.iacr.org/2008/421
Search ePrint
Search Google
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=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.
BibTeX
@misc{eprint-2008-18129,
  title={Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme},
  booktitle={IACR Eprint archive},
  keywords={perfectly secure message transmission, information theoretic security},
  url={http://eprint.iacr.org/2008/421},
  note={This is a revised version of Eurocrypt 2008. kurosawa@mx.ibaraki.ac.jp 14218 received 30 Sep 2008, last revised 5 Dec 2008},
  author={Kaoru Kurosawa and Kazuhiro Suzuki},
  year=2008
}