Cheating Detectable Secret Sharing Schemes for Random Bit Strings

In secret sharing scheme, Tompa and Woll considered a problem of cheaters who try to make another participant reconstruct an invalid secret. Later, some models of such cheating were formalized and lower bounds of the size of shares were shown in the situation of fixing the minimum successful cheating probability. Under the assumption that cheaters do not know the distributed secret, no efficient scheme is known which can distribute bit strings. In this paper, we propose an efficient scheme for distributing bit strings with an arbitrary access structure. When distributing a random bit string with threshold access structures, the bit length of shares in the proposed scheme is only a few bits longer than the lower bound.