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

Kaoru Kurosawa; Kazuhiro Suzuki

Paper 2007/076

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

Kaoru Kurosawa and Kazuhiro Suzuki

Abstract

It is known that perfectly secure (-round, -channel) message transmission (MT) schemes exist if and only if , where is the number of channels that the adversary can corrupt. Then does there exist an {\it almost} secure MT scheme for ? 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 (-round, -channel) MT schemes for .

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: Private and reliable transmission information theoretic security communication efficiency
Contact author(s): kurosawa @ mx ibaraki ac jp
History: 2007-05-07: revised; 2007-02-28: received; See all versions
Short URL: https://ia.cr/2007/076
License: CC BY

BibTeX

@misc{cryptoeprint:2007/076,
      author = {Kaoru Kurosawa and Kazuhiro Suzuki},
      title = {Almost Secure (1-Round, n-Channel) Message Transmission Scheme},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/076},
      year = {2007},
      url = {https://eprint.iacr.org/2007/076}
}