Detection of cheaters in vector space secret sharing schemes

A perfect secret sharing scheme is a method of distributing shares of a sec ret among a set P of participants in such a way that only qualified subsets of P can reconstruct the secret from their shares and non-qualified subset s have absolutely no information on the value of the secret. In a secret sh aring scheme, some participants could lie about the value of their shares i n order to obtain some illicit benefit. Therefore, the security against che ating is an important issue in the implementation of secret sharing schemes . Two new secret sharing schemes in which cheaters are detected with high p robability are presented in this paper. The first one has information rate equal to 1/2 and can be implemented not only in threshold structures, but i n a more general family of access structures. We prove that the information rate of this scheme is almost optimal among all schemes with the same secu rity requirements. The second scheme we propose is a threshold scheme in wh ich cheaters are detected with high probability even if they know the secre t. The information rate is in this case 1/3. In both schemes, the probabili ty of cheating successfully is a fixed value that is determined by the size of the secret.