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

Date Added: Oct 2009
Format: PDF

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 the authors 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. They deduce a necessary and sufficient condition for the existence of such schemes, and they show how to reduce the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms.