ABSTRACT: Key predistribution schemes (KPSs) and one-time broadcast encryption schemes (OTBESs) are unconditionally secure protocols for key distribution in networks. The efficiency of these schemes has been measured in previous works in terms of their information rate, that is, the ratio between the length of the secret keys and the length of the secret information that must be stored by every user. Several constructions with optimal information rate have been proposed, but in them the secret keys are taken from a finite field with at least as many elements as the number of users in the network. This can be an important drawback in very large networks in which the nodes have limited computational resources. Actually, key predistribution schemes have been applied recently in the design of key distribution protocols for such scenario. In this paper we present a method to construct key predistribution schemes from linear codes that provide new families of KPSs and OTBESs for an arbitrarily large number of users and with secret keys of constant size. As a consequence of the Gilbert-Varshamov bound, we can prove that our KPSs are asymptotically more efficient than previous constructions, specially if we consider KPSs that are secure against coalitions formed by a constant fraction of the users. We analyze as well the KPSs that are obtained from families of algebraic geometry linear codes that are above the Gilbert-Varshamov bound, as the ones constructed from the curves of Garcia and Stichtenoth. Finally, we discuss how the use of KPSs based on algebraic geometry codes can provide more efficient OTBESs.
This is a joint work with Hao Chen, San Ling, Huaxiong Wang, and Chaoping Xing.

ABSTRACT: In a secret sharing scheme a secret value is distributed into shares among a set of participants in such a way that the qualified subsets of participants can recover the secret value, while the non-qualified ones do not obtain any information about it. In this situation, the size of every share is at least the size of the secret. If all shares have the same size as the secret, which is the best possible situation, the scheme is said to be ideal. Only a few access structures admit an ideal secret sharing scheme. In general, one is interested in finding schemes with optimal share length for every given access structure. This appeared to be a very difficult problem that has attracted the attention of many researchers. Nevertheless, it is far from being solved. Several methods to find both lower and upper bounds on the share length will be discussed in this talk. We present the most important results and techniques that have been obtained about this open problem from combinatorics, specially from the use of matroids and polymatroids. We discuss as well some combinatorial techniques to construct efficient linear secret sharing schemes.