Threshold Schemes from Combinatorial Designs

Abstract

Informally, a $(t,w,v;m)$-threshold scheme is a way of distributing partial information (chosen from a set of $v$ shadows) to $w$ participants, so that any $t$ of them can easily calculate one of $m$ possible keys, but no subset of fewer than $t$ participants can determine the key. A perfect threshold scheme is one in which no subset of fewer than $t$ participants can determine any partial information regarding the key. In this paper, we study the number $M(t,w,v)$, which denotes the maximum value of $m$ such that a perfect $(t,w,v;m)$-threshold scheme exists. It has been shown previously that$M(t,w,v)\le (v-t+1)/(w-t+1)$, with equality occurring if and only if there is a Steiner system $S(t,w,v)$ that can be partitioned into Steiner systems $S(t-1,w,v)$. In this paper, we study the numbers $M(t,w,v)$ in some cases where this upper bound cannot be attained. Specifically, we determine improved bounds on the values $M(3,3,v)$ and $M(4,4,v)$.