Error Decodable Secret Sharing and One-Round Perfectly Secure Message Transmission for General Adversary Structures

Keith M.  Martin; Maura B.  Paterson; Douglas R.  Stinson

Paper 2009/487

Error Decodable Secret Sharing and One-Round Perfectly Secure Message Transmission for General Adversary Structures

Keith M. Martin, Maura B. Paterson, and Douglas R. Stinson

Abstract

An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper we consider schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure, thus generalising both a related notion studied by Kurosawa, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. We deduce a necessary and sufficient condition for the existence of such schemes, and we show how to reduce the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms. In addition, we explore the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes, and we exploit this connection to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: secret sharing perfectly secure message transmission error correction
Contact author(s): m paterson @ bbk ac uk
History: 2009-10-05: received
Short URL: https://ia.cr/2009/487
License: CC BY

BibTeX

@misc{cryptoeprint:2009/487,
      author = {Keith M.  Martin and Maura B.  Paterson and Douglas R.  Stinson},
      title = {Error Decodable Secret Sharing and One-Round Perfectly Secure Message Transmission for General Adversary Structures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/487},
      year = {2009},
      url = {https://eprint.iacr.org/2009/487}
}