Computational experiments on the analysis of ideal sharing secrets schemes

Gabriel Ruiz-Hernández
Fac. de Ciencias, UNAM
garuher@starmedia.com

Guillermo Morales-Luna
Section de Computation
CINVESTAV-IPN
gmorales@cs.cinvestav.mx

URL:   http://delta.cs.cinvestav.mx/~gmorales

 
 

Abstract:

Resumen en español

A secret sharing scheme gives a procedure to divide any secret into a collection of shares and a distribution of the shares among participants in order to allow just determined access sets of participants to re-construct the whole secret. The access structure (AS) consists of the access sets. Naturally, any AS can be assumed monotone: The sets containing access sets are also access sets.

In any AS the information rate for each participant p is $\rho(p)=\mathop{\rm Max}_{s}\frac{\log \vert s\vert}{\log \vert S\vert}$, where s varies on the shares assigned to p, S is the secret and $\vert\cdot\vert$ denotes the ``length'' function on bits strings. The AS is ideal if $\mathop{\rm Max}_{p}\rho(p)=1$.

If an AS is built over a set $V=\{p_1,\ldots,p_n\}$, a matroid ${\cal M}$ defined over the set $V\cup\{p_0\}$ is said to be appropiate for the AS if the collection of minimal sets in AS coincides with the set

$$\{C-\{p_0\}\vert C\subset V\cup\{p_0\},p_0\in C,C\mbox{ is minimal dependent in }{\cal M}\}.$$

AS's and appropiate matroids are dual notions. In [1] it is shown that for any ideal AS there is a matroid appropiate for the AS. Even more, if for any AS there is a matroid appropiate for the AS such that the matroid is representable in a finite field, then the AS is ideal.

Since then, it has been appeared a challenging question: Decide whether the ideality of the AS implies by itself that any appropiate matroid is representable.

We have followed a computational approach to check this conjecture, exhaustively for small values of n. We generate a matroid, uniformly over all possibilities, we check whether it is representable and in such case we proceed to test whether the AS for which it is appropiate is ideal or not.

Up to now the conjecture prevails. Our programs also provide a Monte-Carlo procedure to count the representable matroids among all possible matroids in finite structures.

Key words: Secret sharing schemes, ideal access structures, matroid representability.

Resumen:

El problema de compartition de secretos se plantea como dividir un secreto s en varios fragmentos, de manera que se pueda dar a conocer a cada participante uno o varios fragmentos, mas sin embargo el secreto ha de ser reconstructible sólo con la participation de grupos privilegiados de participantes. Un conjunto de participantes que mancomunados reconstruyen un secreto se dice ser de acceso. La estructura de acceso (EA) de un tal esquema de compartition de secretos (ECS) es la colection de conjuntos de acceso.

En un ECS, la tasa de information de un participante p es $\rho(p)=\mathop{\rm Max}_{s}\frac{\log \vert s\vert}{\log \vert S\vert}$ donde s varía en los fragmentos asignados a p, S es el secreto total y el tamaño |t| es la longitud en bits de la cadena binaria t. El ECS es ideal si $\mathop{\rm Max}_{p}\rho(p)=1$. Una estructura de acceso es ideal si se puede construir sobre ella un ECS ideal.

Por otro lado, dada una EA sobre un conjunto de n participantes $V=\{p_1,\ldots,p_n\}$, un matroide ${\cal M}$ sobre el conjunto $V\cup\{p_0\}$, se dice que es apropiado para la EA si la colection de elementos minimales de EA coincide con

$$\{C-\{p_0\}\vert C\subset V\cup\{p_0\},p_0\in C,C\mbox{ es dependiente minimal en }{\cal M}\}$$

Para un matroide ${\cal M}$ se construye fácilmente una EA para la que sea apropiado. En este sentido, una EA y su matroide apropiado son duales uno del otro. En [1] se muestra que para toda EA ideal existe un matroide apropiado. Más aún, se ve que si para una EA existe un matroide apropiado que es además representable en un campo finito, entonces la EA es ideal.

El recíproco es una conjetura abierta a la fecha, es decir, se busca demostrar que, en efecto, si el matroide apropiado no fuese representable entonces la EA no podría ser ideal.

En el presente trabajo nos hemos abocado a la revisión computacional exhaustiva de este recíproco, en estructuras pequeñas: Generando uniformemente en todas las posibilidades un matroide, se revisa si es o no representable. Cuando no lo sea, se investiga si acaso la EA de la que es apropiado es o no ideal. En tanto que no lo sea, la conjetura se refuerza. Naturalmente, a la fecha no hemos encontrado un ejemplo que refute la conjetura.

Palabras claves: Compartición de secretos, estructuras ideales, representación de matroides.
 

2000-11-28