Menu
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.