In a secret sharing scheme a secret value is distributed into shares among a set of participants in such a way that the qualified subsets of participants can recover the secret value, while the non-qualified ones do not obtain any information about it. In this situation, the size of every share is at least the size of the secret. If all shares have the same size as the secret, which is the best possible situation, the scheme is said to be ideal. Only a few access structures admit an ideal secret sharing scheme. In general, one is interested in finding schemes with optimal share length for every given access structure. This appeared to be a very difficult problem that has attracted the attention of many researchers.
Nevertheless, it is far from being solved.
Several methods to find both lower and upper bounds on the share length will be discussed in this talk. We present the most important results and techniques that have been obtained about this open problem from combinatorics, specially from the use of matroids and polymatroids. We discuss as well the proven limitations of the known methods to solve this problem.
Copyright. All Rights Reserved.