Mathematics of Secret Sharing

Monday January 25

Carles Padró (Universitat Politècnica de Catalunya)
Ideal Hierarchical Secret Sharing Schemes search of efficient constructions of ideal schemes for families of non-threshold access structures that may have useful applications has attracted a lot of attention. Several proposals have been made for access structures with hierarchical properties, in which the participants are distributed into levels that are hierarchically ordered.

Here, we study hierarchical secret sharing in all generality by providing a natural definition for the family of the hierarchical access structures. Specifically, an access structure is said to be hierarchical if every two participants can be compared according to the following natural hierarchical order: whenever a participant in a qualified subset is substituted by a hierarchically superior participant, the new subset is still qualified.

We present a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. We use the well known connection between ideal secret sharing and matroids and, in particular, the fact the every ideal access structure is a matroid port. In addition, we use recent results on ideal multipartite access structures and the connection between multipartite matroids and discrete polymatroids. We prove that every ideal hierarchical access structure is the port of a representable matroid and, more specifically, we prove that every ideal structure in this family admits ideal linear secret sharing schemes over fields of all characteristics. This generalizes previous results on weighted threshold access structures. Finally, we use our results to find a new characterization of the ideal weighted threshold access structures that is more precise than the existing one.

This is a joint work with Oriol Farràs

Ignacio Cascudo (University of Oviedo, Spain)
Asymptotically good linear secret sharing with strong multiplication over any finite field

Linear secret sharing schemes(LSSS) with an extra algebraic property known as t-strong multiplication have important cryptographic applications: multiparty computation protocols can be based upon such schemes (Cramer, Damgaard, Maurer, Eurocrypt 2000); and more recently, Ishai, Kushilevitz, Ostrovsky and Sahai have found important applications in zero knowledge (STOC 07) and correlation extractions (FOCS 09) as well. For all these uses it is crucial to study the existence of asymptotically good families of LSSSs over fixed finite fields, i.e., families of LSSSs with an unbounded number of shares and strong multiplication for a constant fraction of the shares. A series of results, which relate this problem to interesting questions in code theory and towers of algebraic function fields, were given by Chen and Cramer in Crypto 2006 and Cascudo, Chen, Cramer, Xing in Crypto 2009 and in subsequent work and will be presented in this talk.

László Csirmaz (Central European University, Budapest)
Secret sharing on infinite structures

Traditionally, secret sharing is restricted to finite access structures. This poses no problem in the main field of applications. For finite structures we have a complete picture, at least in the case of perfect secret sharing. When one tries to extend the results for infinitely many participants, technical difficulties arise immediately. How to define the size of the share relative to that of the secret, as entropy, in general, can only be defined for discrete random variables. Even the existence of appropriate (measurable) random variables are far from being trivial. One can easily get mislead by the analogy to the finite case. For example, if F is a finite field, then shifting the field by a random element makes a perfect homeomorphic (with respect to addition) hiding. However when the field is the set of reals, then any probability distribution leaks some information (as taught in statistics classes). One of the first geometrical secret sharing construction using projective planes by Blakley and Swanson is also problematic. While the distribution is homogenous, when taking the conditional distribution given several shares, the result is concentrated on a zero measure set.

We overcome some of the difficulties mentioned above by defining secret sharing on an infinite structure as the limit of its finite restrictions. We justify the soundness of this notion, and give examples showing the non-triviality of the notion.

František Matúš (Academy of Sciences, Prague)
Ideal secret sharing, matroids and relative entropy

In an information-theoretical setting, a secret sharing scheme (sss) can be described by a discrete random vector with finitely many values which satisfies the constraints on Shannon entropies of subvectors corresponding to cryptographic requirements on the access to the secret. A sss is ideal if each participant has at most as much information as the dealer distributing the secret. Ideal sss's with the same access structure are known to correspond to special representations of a matroid. We will review the results and open problems on the resulting classes of representations and matroids. They are closely related to entropic polymatroids, their limits and information theoretical inequalities among Shannon entropies. Ideal sss's with a given access structure and the size of secret will be interpreted as the statistically least favorable cases of the maximum likelihood estimation problems in families of Gibbs distributions.