On Algorithms for Searching a Consistent Set of Shares in a Threshold Scheme and the Related Covering Problem

Abstract

In the Shamir $(k,n)$ threshold scheme, if one or more of the $n$ shares are fake, then the secret may not be reconstructed correctly by some sets of $k$ shares. Supposing that at most $t$ of the $n$ shares are fake, Rees et al. (1999) described two algorithms to determine consistent sets of shares so that the secret can be reconstructed correctly from $k$ shares in any of these consistent sets. In their algorithms, no honest participant can be absent and at least $n–t$ shares should be pooled during the secret reconstruction phase. In this paper, we propose a modified algorithm for this problem so that the number of participants taking part in the secret reconstruction can be reduced to $k+2t$ and the shares need to be pooled can be reduced to, in the best case, $k+t$, and less than or equal to $k+2t$ in the others. Its performance is evaluated. A construction for $t$-coverings, which play key roles in these algorithms, is also provided.