• Calendar

June 18, Wednesday
12:00 – 13:00

Secret-sharing schemes are an important tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only pre-defined authorized subsets of participants can reconstruct the secret from their shares. The collection of pre-defined authorized subsets is called an access structure.

In this talk we will discuss ideal secret sharing schemes, that is, schemes in which the shares are taken from the same domain as the secrets (the domain of shares cannot be smaller). Brickell and Davenport have shown an interesting connection between ideal secret sharing schemes and matroids – a combinatorial structure that generalizes the linear independence. They give a necessary condition for an access structure to have an ideal secret sharing scheme – the access structure must be induced by a matroid. Seymour has proved that the necessary condition is not sufficient: There exists an access structure induced by the Vamos matroid that does not have an ideal scheme. We strengthen the result of Seymour by showing that the access structure induced by the Vamos matroid does not have a scheme that is close to being ideal. Our bounds are obtained by using non-Shannon inequalities for the entropy function.

The talk is based on joint works with Carles Padro and Noam Livne.