Optimizing secret sharing schemes for general access structure

A secret sharing scheme is a method to distribute a secret value into shares in such a way that only some qualified subsets of participants are able to recover the secret from their shares. The family of the qualified subsets is the access structure of the scheme. Determining the optimal complexity of secret sharing schemes for any given access structure is a very difficult and long-standing open problem, which involves varied and deep mathematical techniques. This talk is a survey about the last results on this problem.

A special stress will be put on the connections between matroids and ideal secret sharing schemes, that is, schemes with minimum-length shares. In particular, some recent results about the length of the shares in secret sharing schemes for the Vamos matroid, in a joint work with Amos Beimel and Noam Livne, will be presented. Specifically, non-Shannon inequalities for the entropy function are used for the first time in secret sharing to find the first example of a matroid in which the length of the shares is larger than the length of the secret by a constant factor.