A Combinatorial Approach to Threshold Schemes

Abstract

We investigate the combinatorial properties of threshold schemes. Informally, a $( t,w )$-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key, but no subset of fewer than t participants can determine the key. Our interest is in perfect threshold schemes: no subset of fewer than t participants can determine any partial information regarding the key. We give a combinatorial characterization of a certain type of perfect threshold scheme. We also investigate the maximum number of keys that a perfect $( t,w )$-threshold scheme can incorporate, as a function of $t,w$, and the total number of possible shadows, $v $. This maximum can be attained when there is a Steiner system $S( t,w,v )$ that can be partitioned into Steiner systems $S ( t - 1,w,v )$. Using known constructions for such Steiner systems, we present two new classes of perfect threshold schemes, and discuss their implementation.