THE DETECTION OF CHEATERS IN THRESHOLD SCHEMES

Informally, a (t, w)-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key (or secret), but no subset of fewer than t participants can determine the key. Presented in this paper is an unconditionally secure threshold scheme in which any cheating participant can be detected and identified with high probability by any honest participant, even if the cheater is in coalition with other participants. Also given is a construction that will detect with high probability a dealer who distributes inconsistent shadows (shares) to the honest participants. The scheme is not perfect; a set of t - 1 participants can rule out at most 1 + t-1w-t+1) possible keys, given the information they have. In this scheme, the key will be an element of GF(q) for some prime power q. Hence q can be chosen large enough so that the amount of information obtained by any t - 1 participants is negligible.