CWI Cryptology Group

Abstract: The characterization of the access structures of ideal secret sharing schemes is one of the main open problems in secret sharing. Because of its difficulty, it has been studied for several particular families of access structures. In this talk, we deal with multipartite access structures, that is, structures in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Some particular classes of multipartite structures had been considered in seminal works on secret sharing (Shamir, Simmons, Brickell) and these and other classes have been studied recently by several authors (Tassa, Beimel et al, Herranz and Saez). In this work, multipartite access structures are studied with all their generality. Since every access structure is multipartite, our goal is perhaps too challenging, because it implies solving the general open problem of the characterization of all access ideal access structures. Nevertheless, our results can be seen as an attack to this general open problem under a different point of view. We present some necessary conditions and some sufficient conditions for an access structure to be ideal in terms of the classification of its participants into equivalence classes. These conditions can be specially useful if the number of classes is small or these classes are distributed in some special way.
More specifically, our results are the following:
1. We present a characterization of matroid-related access structures. To do that, we introduce multipartite matroids and we relate them to discrete polymatroids, a combinatorial object that has been introduced recently by Herzog and Hibi because of its implications with several problems in commutative algebra. As a consequence of this characterization, some necessary conditions for a multipartite access structure to be ideal are obtained.
2. We define a special class of discrete polymatroids: the linearly representable ones. We use these discrete polymatroids to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal.
3. We apply those general results to several families of multipartite access structures. First, we study the tripartite access structures. We obtain a complete characterization of the ideal structures in this family and we prove that the tripartite matroid-related access structures coincide with the ideal ones. Second, we study the hierarchical access structures studied by Tassa (TCC 2004) and other families of multipartite access structures introduced by Brickell and studied afterwards by Tassa (ICALP 2006).

Abstract: We describe Lenstra's `scan algorithm' to enumerate all reduced Arakelov divisors in given open set in the Arakelov class group. This algorithm is a generalization of the classical continued fraction algorithm for real quadratic fields.

Abstract: In this talk I present a method for explicitly constructing towers of curves defined over a finite field with many rational points. A motivation for studying these towers is an application to coding theory. An interesting feature of the method is that one obtains equations for the whole towers, starting from equations for the first few levels. A key ingredient is the study of solutions of differential equations in positive characteristic.