CWI Cryptology Group

Abstract: The aim of this talk is to present and discuss some recent results and several open problems about the characterization of the access structures of ideal secret sharing schemes. It is well known that Matroids play a key role in that characterization. Specifically, the most important problems are to determine which access structures are matroid-related and which matroids can be represented by an ideal secret sharing scheme (or ss-represented). Some important results and techniques on this latter question were given by Simonis and Ashikhmin (1998) and by Matus (1999).
Several authors have attacked those problems by restricting them to some families of access structures. The latest works on that line deal with hierarchical access structures (Tassa, TCC 2004) and weighted threshold access structures(Beimel, Tassa, Weinreb, TCC 2005).
We present in this talk our recent unpublished results dealing with two other families: the ones whose minimal qualified subsets have at most three participants and the tripartite ones, in which the set of participants is divided into three parts, and all players in each one of those parts play an equivalent role in the structure.
For the first family, we characterize all the structures that are matroid-related and we prove that the optimal information rate of a non-matroid-related access structure in that family is at most 2/3. Moreover, we prove that if such an structure is related to a matroid with rank greater than 3, then it can be realized by an ideal linear secret sharing scheme. Therefore, the only question to be solved is to determine which matroids with rank 3 can be ss-represented. To do that, one should definitely use the results and techniques given by Matus (1999).
The value 2/3 appear as an upper bound for non-matroid-related access structures in many previously studied families. So, we wonder to which extend this result can be generalized and we discuss how polymatroids could be used to answer this question. Another open question is to find bounds on the optimal information rate of the access structures that are related to non-ss-representable matroids.

Abstract: The Number Field Sieve is asymptotically the fastest algorithm for factoring a large integer N with no small prime factors, such as an RSA modulus. An early step in the algorithm selects two polynomials with a common root modulo N. This talk will present some techniques for choosing the polynomials when N has no nice algebraic form.

Abstract: Shamir secret sharing is used in many (if not most) multi-party computation protocols that are known nowadays. In 1992, Franklin and Yung showed that increasing the tolerance for eavesdroppers by a constant allows for schemes that are more efficient by a linear factor. We show a variant of their scheme and applications in the areas of perfectly secure message transmission and secure multiplication of elements in extension fields of finite fields.

Abstract: A black-box secret sharing scheme (BBSSS) for a given access structure works in exactly the same way over any finite Abelian group, as it only requires black-box access to group operations and to random group elements. In particular, there is no dependence on e.g. the structure of the group or its order. The expansion factor of a BBSSS is the length of a vector of shares (the number of group elements in it) divided by the number of players $n$.
In 2002 Cramer and Fehr proposed a threshold BBSSS with an asymptotically minimal expansion factor $\Theta(\log n)$.
We present a BBSSS that is based on a new paradigm, namely, primitive sets in algebraic number fields. This leads to a new BBSSS with an expansion factor that is absolutely minimal up to an additive term of at most 2, which is an improvement by a constant additive factor. The construction uses techniques from algebraic number theory as well as algebraic geometry.
We provide good evidence that our scheme is considerably more efficient in terms of the computational resources it requires. Indeed, the number of group operations to be performed is $\tilde{O}(n^2)$ instead of $\tilde{O}(n^3)$ for sharing and $\tilde{O}(n^{1.6})$ instead of $\tilde{O}(n^{2.6})$ for reconstruction. Finally, we show that our scheme, as well as that of Cramer and Fehr, has asymptotically optimal randomness efficiency.
This is talk is based on joint work with Serge Fehr, Hendrik Lenstra, and Martijn Stam. An article with these results appears in the Proceedings of the 25th Annual IACR CRYPTO Conference, 2005.