Algorithms for Detecting Cheaters in Threshold Schemes

Abstract

In a $(k,n)$-threshold scheme, a secret key $K$ is split into $n$ shares in such a way that $K$ can be recovered from $k$ or more shares, but no information about $K$ can be obtained from any $k-1$ or fewer shares. We are interested in the situation where there are some number of incorrect (i.e., faulty) shares. When there are faulty shares, we might need to examine more than $k$ shares in order to reconstruct the secret correctly. Given an upper bound, namely $t$, on the number of faulty shares, we focus on finding efficient algorithms for reconstructing the secret in a $(k,n)$-threshold scheme. We call this the threshold scheme with cheaters problem.

We first review known combinatorial algorithms that use covering designs, as presented in Rees et al. [11] and Tso et al. [13]. Then we extend the ideas of their algorithms to a more general one. We also link the threshold scheme with cheaters problem to decoding generalized Reed-Solomon codes. Then we adapt two decoding algorithms, namely, the Peterson-Gorenstein-Zierler Algorithm and Gao’s Algorithm, to solve our problem. Finally, we contribute a general algorithm that combines both the combinatorial and decoding approaches, followed by an experimental analysis of all the algorithms we describe.