CWI Cryptology Group

Abstract: Due to the difficulty (presumably, impossibility) of finding an efficient secret sharing scheme for every access structure, the search of ideal schemes for access structures that have interesting properties for the applications of secret sharing is worth considering. This line of research was initiated shortly after the invention of secret sharing. Several constructions of ideal secret sharing schemes for multipartite access structures have been presented. In such an access structure, the participants are divided into several parts and participants in the same part play an equivalent role in the structure. This kind of access structures are the most natural generalization of the threshold ones. Several of those constructions deal with hierarchical access structures, in which the participants can be hierarchically ordered according to their power to contribute into recovering the secret.
In spite of all the existing constructions, the problem of determining the multipartite access structures that admit an ideal secret sharing scheme had not been attacked until recently. The first general results on this problem were presented in our paper in Eurocrypt 2007. The main contribution of this work is the use of integer polymatroids to describe and analyze multipartite matroids. In particular, the existence of linear representations of multipartite matroids is characterized by means of much simpler linear representations of integer polymatroids. The power of these results has been demonstrated by providing a characterization of ideal tripartite access structures and, more importantly, a complete characterization of ideal hierarchical access structures that has been presented in TCC 2010.
Even though our general results provide a complete framework for the construction of ideal multipartite secret sharing schemes, a number of questions are still open in relation to the efficiency of such constructions. The most remarkable among them is to minimize the size of the field over which such an access structure admits an ideal secret sharing scheme.

Abstract: A word in a linear error-correcting code is a basis for the 1-dimensional subcode it spans. This gives the opportunity to generalize results about weights and supports of codewords to weights and supports of subcodes of a given dimension. Many theorems in coding theory have been generalized to this "higher-dimensional" coding theory, for example the MacWilliams relations. We will have a look at two properties of a code and their relation with matroid theory, and the generalization of this relations to subcodes.
The weight enumerator of a code has as coefficients the number of words of a given weight. This polynomial is determined by the Tutte polynomial of the matroid associated by the code, but not vice versa. We will see how the generalized weight enumerator can be computed, and how this method implies that the generalized weight enumerators and the Tutte polynomial completely determine each other.
As a second application of looking at subcodes instead of words, we consider minimal subcodes. Minimal codewords have minimal support with respect to inclusion, and their supports are exactly the cocircuits of the matroid associated to the code. The minimal supports of all r-dimensonal subcodes are also the cocircuits of some matroid that turns out to be the r-th truncation of the matroid associated to the code.

Abstract: Constructing secret sharing with infinitely many participants has many challenges which prevents immediate generalizations of the usual constructions. In case of threshold structures, for example, it is the lack of a translation invariant probability measure on infinite fields. The geometric construction of Blakley and Swanson from 1986 based on projective planes misses the independence between the shares and the secret. In the first part of the talk I will present a solution for the 2-threshold system with infinitely many participants and, in general, describe access structure for which a perfect secret sharing scheme exist. We consider some exotic examples for ramp schemes, where non-qualified sets required not to have full information on the secret. The first part is concluded by several intriguing open problems.
In the second half of the talk I generalize the complexity (or efficiency) of secret sharing schemes over countably many participants. I apply the notion for graphs, and discuss results for a couple of infinite graphs.