An Application of Covering Designs: Determining the Maximum Consistent set of Shares in a Threshold Scheme

The shares in a \((k,n)\) Shamir threshold scheme consist of \(n\) points on some polynomial of degree at most \(k-1\). If one or more of the shares are faulty, then the secret may not be reconstructed correctly. Supposing that at most \(\epsilon\) of the \(n\) shares are faulty, we show how a suitably chosen covering design can be used to compute the correct secret. We review known results on coverings of the desired type, and give some new constructions. We also consider a randomized algorithm for the same problem, and compare it with the deterministic algorithm obtained by using a particular class of coverings.