Almost Secure (1-Round, n-Channel) Message Transmission Scheme

Kaoru KUROSAWA  Kazuhiro SUZUKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.1   pp.105-112
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.105
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Secure Protocol
private and reliable transmission,  information theoretic security,  communication efficiency,  

Full Text: PDF>>
Buy this Article

It is known that perfectly secure (1-round, n-channel) message transmission (MT) schemes exist if and only if n ≥ 3t+1, where t is the number of channels that the adversary can corrupt. Then does there exist an almost secure MT scheme for n=2t+1 ? In this paper, we first sum up a number flaws of the previous almost secure MT scheme presented at Crypto 2004. 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.