   Next:Main factsUp:Computational experiments on thePrevious:Motivation

# Basic definitions

Let be a set of secrets (i.e., words in a finite alphabet).

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.

Equation means:

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:
1.
Each secret should be recovered by the shares on sets in : For each there is a function such that for any and  2.
If V1 is not in , no partial information can be recovered from the shares on V1 (from the information theoretic point of view): If we write then for any and , On any SSS , the information ratio of participant p is where s varies on the assigned shares to p, S is the total secret and is the size function: for any bit string t, |t| is its length in bits. 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 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 Si coincide.

A matroid is of the form where E is the ground set, and , whose elements are called independent sets, satisfies:

(I1) .
(I2)
If and then .
(I3)
If X, Y are in with |X|=|Y|+1, there exists such that .
Each vector space determines a matroid:
• the ground set is the vector space,
• any linearly independet set of vectors is independent.

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.   Next:Main factsUp:Computational experiments on thePrevious:Motivation
Guillermo Morales-Luna

2000-11-28