Basic definitions

Let ${\cal S}$ be a set of secrets (i.e., words in a finite alphabet).

A secret sharing scheme (SSS) is of the form ${\cal E}=(V,\Pi,{\cal V})$, with access structure${\cal V}\subset {\cal P}(V)$ and $\Pi$ a function ${\cal S}\times R \to {\cal S}_1\times \cdots \times {\cal S}_n$, where each set ${\cal S}_i$ consists of the possible shares to be assigned to participant v_i, $i\leq n$, and R is a colection of random values.

Equation $(s_1, \cdots ,s_n)=\Pi(S,r)$ means:

The secret S, with the random value r is ``split'' into te shares $s_1,\ldots,s_n$ and each s_i is given to participant v_i, $i\leq n$.

Let's write $s_i=\Pi_i(S,r)$,$i\leq n$. The following conditions must be accomplished:

1.

Each secret should be recovered by the shares on sets in ${\cal V}$: For each $V_0\in {\cal V}$ there is a function $\Sigma_{V_0}:\prod_{v\in V_0}{\cal S}_v \to {\cal S}$ such that for any $S\in{\cal S}$ and $r\in R$: $S=\Sigma_{V_0}\left[\Pi_v(S,r)\right]_{v\in V_0}.$

2.

If V₁ is not in ${\cal V}$, no partial information can be recovered from the shares on V₁ (from the information theoretic point of view): If we write

$$\left[\left.\left[s_i\right]_{i=1}^n\right\vert S\right] \equiv \left[\forall v\in V_1: s_v=\Pi_v(S,r)\right]$$

then for any $S,T\in{\cal S}$ and $\left[s_i\right]_{i=1}^n\in \prod_{i=1}^n{\cal S}_i$,

$$\mbox{Prob}\left(\left\{r\in R\vert\left[\left.\left[s_i\righ......eft.\left[s_i\right]_{i=1}^n\right\vert T\right]\right]\right).$$
 
 

On any SSS ${\cal E}$, the information ratio of participant p is $\rho_{\cal E}(p)=\mathop{\rm Max}_{s}\frac{\log \vert s\vert}{\log \vert S\vert}$ where s varies on the assigned shares to p, S is the total secret and $t\mapsto \vert t\vert$ is the size function: for any bit string t, |t| is its length in bits.

${\cal E}$ is information-ideal (I-ideal) if $\mathop{\rm Max}_{p}\rho_{\cal E}(p)=1$.
 

An AS is I-ideal if there is an I-ideal SSS ${\cal E}$ over that AS.
 
 

As an alternative approach, for any AS ${\cal V}$, a minimal access set is V₀ such that

$$\forall V_1\in {\cal V}: \ V_1\subset V_0 \ \Rightarrow\ V_1 = V_0.$$

Let ${\cal V}_{\mbox{\scriptsize Min}}=\{V_0\in {\cal V}\vert V_0\mbox{ is minimal}\}$.
If for any $V_0\in {\cal V}_{\mbox{\scriptsize Min}}$, $\mbox{card}(V_0)\geq k$, then the AS ${\cal V}$ is called k out of $n=\mbox{\em card}(V)$.

An SSS $\Pi:{\cal S}\times R \to {\cal S}_1\times \cdots \times {\cal S}_n$ is m-ideal if $m=\mbox{card}(S)$ and for any $i\leq n$, $m=\mbox{card}(S_i)$.

An AS ${\cal V}$ is m-ideal if there is an m-ideal SSS over ${\cal V}$.

${\cal V}$ 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, $i\leq n$ coincide.

A matroid${\cal M}$ is of the form ${\cal M}=(E, {\cal I})$ where E is the ground set, and ${\cal I}\subset{\cal P}(E)$, whose elements are called independent sets, satisfies:

(I1)

$\emptyset \in {\cal I}$.

(I2)

If $X \in {\cal I}$ and $Y \subset X$ then $Y \in {\cal I}$.

(I3)

If X, Y are in ${\cal I}$ with |X|=|Y|+1, there exists $x \in X-Y$ such that $Y \cup \{x\} \in {\cal I}$.

Each vector space determines a matroid:

• the ground set is the vector space,
• any linearly independet set of vectors is independent.

 
 

In any matroid ${\cal M}=(E, {\cal I})$ 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 $I\!\! K$ if there is a $k\in I\!\!N$ and a map $\phi:{\cal P}({\cal P}(E))\to {\cal P}({\cal P}(I\!\! K^k))$ that preserves dependency:

$$\forall I\in {\cal P}({\cal P}(E)):\ I\in{\cal I}\ \Leftrightarrow\ \phi(I) \mbox{ is l. i.}$$  

Proposition 2.2   If $n=\mbox{\em card}(E)$, let $\mu_n$ be the number of non-isomorphic matroids with ground set E. Then:

$$n-\frac{3}{2}\log_2 n + O\left(\log_2\log_2 n\right) \leq \log_2\log_2 \mu_n \leq n- \log_2 n + O\left(\log_2\log_2 n\right).$$

Roughly speaking: The growth of $\mu_n$ is greater than doubly exponential.
 
 

Suppose given an AS ${\cal V}$ over a set of n participants $V=\{p_1,\ldots,p_n\}$. A matroid ${\cal M}=(V\cup\{p_0\},{\cal I})$, with $p_0\not\in V$, with independent sets ${\cal I}\subset {\cal P}(V\cup\{p_0\})$, is appropriate for ${\cal V}$ if ${\cal V}$ can be realized as the traces over V of the collection of circuits on ${\cal M}$:

$$\forall I\in {\cal P}({\cal P}(V)):\ I\in{\cal V}\ \Leftright......\}: C\mbox{ is a circuit }\&\ p_0\in C\ \&\ I\subset C-\{p_0\}.$$

p₀ plays the role of a dealer distributing the shares among the participants v_i.

2000-11-28