MDS secret sharing schemes secure against cheaters

In secret sharing schemes (SS), cheaters may open forged shares so that honest participants would recover a forged secret. This problem is closely related to error correcting codes. For an SS, consider a code C such that a codeword is a possible (υ₁,…,υ _n), where υ_i is a share of participant P_i. Let d_min denote the minimum Hamming distance of C. Then cheaters can be detected from (υ₁,…,υ_n) if up to [(d_min -1)/2] participants are cheaters. McEliece and Sarwate (1981) showed that d_min=n-k+1 for Shamir´s (1979) (k,n)-threshold scheme. Karnin et al. (1982) showed this equality for any ideal (k,n)-threshold scheme. (Blakeley and Kabatianskii (1995) showed another proof.) On the other hand, (k,n)-threshold schemes were generalized to monotone access structures Γ, where ΓΔ={A|A can determine the secret} (Itoh et al. 1993). This paper first proves d_min⩽n-max_B∉Γ|B| for any monotone access structure Γ. Further, we present an SS which satisfies d _min=n-max_B∉Γ|B| for any Γ. This SS has a maximum distance separable (MDS) property. Third, we introduce a new measure d_cheat as follows. The correct secret s can be recovered from (υ₁,…,υ_n) if there are at most [(d_cheat-1)/2] cheaters. The fact of cheating can be detected from (υ₁,…,υ_n) if there are at most d_cheat-1 cheaters. We prove that d_min ⩽d_cheat=n-max_B∉Γ |B|