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 vi, , and R is a colection of random values.
The secret S, with the random value r is ``split'' into te shares and each si is given to participant vi, .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 V0 such that
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 Si, 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 :
p0 plays the role of a dealer distributing the shares among the participants vi.