Affiliation: Universitat Politecnica de Catalunya
Representing small identically self-dual matroids by self-dual codes
The matroid associated to a linear code is the representable matroid that is defined by the columns of any generator matrix. The matroid associated to a self-dual code is identically self-dual, but it is not known whether every identically self-dual representable matroid can be represented by a self-dual code. This open problem was proposed by Cramer et al ("On Codes, Matroids and Secure Multi-Party Computation from Linear Secret Sharing Schemes", Crypto 2005), who proved it to be equivalent to an open problem on the complexity of multiplicative linear secret sharing schemes. Some contributions to its solution are given in this paper. A new family of identically self-dual matroids that can be represented by self-dual codes is presented. Besides, we prove that every identically self-dual matroid on at most eight points is representable by a self-dual code.
On codes, matroids and secure multi-party computation from linear secret sharing schemes
Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.
Improving the trade-off between storage and communication in broadcast encryption schemes
The most important point in the design of broadcast encryption schemes (BESs) is obtain a good trade-off between the amount of secret information that must be stored by every user and the length of the broadcast message, which are measured, respectively, by the information rate $\rho$ and the broadcast information rate $\rho_B$. In this paper we present a simple method to combine two given BESs in order to improve the trade-off between $\rho$ and $\rho_B$ by finding BESs with good information rate $\rho$ for arbitrarily many different values of the broadcast information rate $\rho_B$. We apply this technique to threshold $(R,T)$-BESs and we present a method to obtain, for every rational value $1/R \le \rho_B \le 1$, a $(R,T)$-BES with optimal information rate $\rho$ among all $(R,T)$-BESs that can be obtained by combining two of the $(R,T)$-BESs proposed by Blundo et al.
Linear broadcast encryption schemes
A new family of broadcast encryption schemes (BESs), which will be called linear broadcast encryption schemes (LBESs), is presented in this paper by using linear algebraic techniques. This family generalizes most previous proposals and provide a general framework to the study of broadcast encryption schemes. We present a method to construct LBESs for a general specification structure in order to find schemes that fit in situations that have not been considered before.