Cryptology ePrint Archive: Report 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=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.

Category / Keywords: perfectly secure message transmission, information theoretic security

Publication Info: This is a revised version of Eurocrypt 2008.

Date: received 30 Sep 2008, last revised 5 Dec 2008

Contact author: kurosawa at mx ibaraki ac jp

Available format(s): PDF | BibTeX Citation

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

Version: 20081205:122026 (All versions of this report)

Short URL: ia.cr/2008/421

Discussion forum: Show discussion | Start new discussion