Cryptology ePrint Archive: Report 2007/076
Almost Secure (1-Round, n-Channel) Message Transmission Scheme
Kaoru Kurosawa and Kazuhiro Suzuki
Abstract: It is known that perfectly secure ($1$-round, $n$-channel) message transmission (MT) schemes exist if and only if $n \geq 3t+1$,
where $t$ is the number of channels that the adversary can corrupt.
Then does there exist an {\it almost} secure MT scheme for $n=2t+1$ ? In this paper, we first sum up a number flaws of the previous {\it almost} secure MT scheme presented at Crypto 2004. (The authors already noted in thier presentation at Crypto'2004 that their scheme was flawed.) We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity
of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure ($1$-round, $n$-channel) MT schemes for $n=2t+1$.
Category / Keywords: cryptographic protocols / Private and reliable transmission, information theoretic security, communication efficiency
Date: received 26 Feb 2007, last revised 6 May 2007
Contact author: kurosawa at mx ibaraki ac jp
Available format(s): PDF | BibTeX Citation
Version: 20070507:045602 (All versions of this report)
Short URL: ia.cr/2007/076
[ Cryptology ePrint archive ]