A Combinatorial Approach to Threshold Schemes
Authors:
- D. R. StinsonDSD. R. Stinson
- S. A. VanstoneSVS. A. Vanstone
- 1 May 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (2) , 230-236
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.
Keywords
This publication has 6 references indexed in Scilit:
- On hiding information from an oracleJournal of Computer and System Sciences, 1989
- The NP-Completeness of Edge-ColoringSIAM Journal on Computing, 1981
- How to share a secretCommunications of the ACM, 1979
- Safeguarding cryptographic keys1979
- Partitioning the planes of AG2m(2) into 2-designsDiscrete Mathematics, 1976
- Some partitions of all triples into steiner triple systems1974