Efficient (k, n) Secret Sharing Scheme Secure against k — 2 Cheaters

In 1989, Tompa and Woll first introduced a cheating problem in Shamir's (k, n) secret sharing scheme, such that malicious shareholders (cheaters) aim to cheat honest shareholders by pooling forged shares during secret reconstruction. They succeed if honest shareholders accept a forged secret. In this cheating, even a single cheater can deceive other k – 1 honest shareholders with high probability. In this paper, we consider a situation that there are k -–2 or less cheaters in secret reconstruction, and propose a (k, n) secret sharing scheme secure against such cheating. Our scheme is efficient respect to the size of shares. Furthermore, our scheme is secure regardless of the probability distribution of the secret.