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