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