Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures
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, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited 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.
secret sharing perfectly secure message transmission error correction