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

Abstract

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 $ϵ$ 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.