A secret sharing scheme (SSS) is of the form , with access structure and a function , where each set consists of the possible shares to be assigned to participant v_{i}, , and R is a colection of random values.
Equation means:
The secret S, with the random value r is ``split'' into te shares and each s_{i} is given to participant v_{i}, .Let's write ,. The following conditions must be accomplished:
then for any
and ,
is information-ideal (I-ideal) if .
An AS is I-ideal if there is an I-ideal SSS
over that AS.
As an alternative approach, for any AS , a minimal access set is V_{0} such that
Let .
If for any , ,
then the AS
is called k out of .
An SSS is m-ideal if and for any , .
An AS is m-ideal if there is an m-ideal SSS over .
is universally ideal if for any m, it is m-ideal.
Proposition 2.1 Any I-ideal AS is universally
ideal if it is combinatorial, i.e. the set of secrets S and
all the shares sets S_{i},
coincide.
A matroid is of the form where E is the ground set, and , whose elements are called independent sets, satisfies:
In any matroid the maximal independent sets are called bases and each base has the same cardinality. This uniform value is the rank of the matroid. Any minimal dependent set is said to be a circuit. The matroid is connected if any two points in the ground set can be included in a circuit. The matroid is representable over a field if there is a and a map that preserves dependency:
Proposition 2.2 If , let be the number of non-isomorphic matroids with ground set E. Then:
Roughly speaking: The growth of
is greater than doubly exponential.
Suppose given an AS over a set of n participants . A matroid , with , with independent sets , is appropriate for if can be realized as the traces over V of the collection of circuits on :
p_{0} plays the role of a dealer distributing the
shares among the participants v_{i}.