Cryptology ePrint Archive: Report 2009/487

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

Keith M. Martin and 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.

Category / Keywords: secret sharing, perfectly secure message transmission, error correction

Date: received 2 Oct 2009

Contact author: m paterson at bbk ac uk

Available format(s): PDF | BibTeX Citation

Version: 20091005:120834 (All versions of this report)

Short URL: ia.cr/2009/487

Discussion forum: Show discussion | Start new discussion