Paper 2004/245

On codes, matroids and secure multi-party computation from linear secret sharing schemes

Ronald Cramer, Vanesa Daza, Ignacio Gracia, Jorge Jimenez Urroz, Gregor Leander, Jaume Marti-Farre, and Carles Padro

Abstract

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.

Note: 23 Sep 2004: Authors' affiliations have been updated. 5 Jan 2007: Publication Info updated. 26 Jan 2007: a new version with major revisions has been uploaded.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper that appeared in Crypto 2005
Keywords
multi-party computationidentically self-dual matroidsself-dual codesefficient error correction
Contact author(s)
matcpl @ mat upc es
History
2007-01-26: last of 4 revisions
2004-09-22: received
See all versions
Short URL
https://ia.cr/2004/245
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/245,
      author = {Ronald Cramer and Vanesa Daza and Ignacio Gracia and Jorge Jimenez Urroz and Gregor Leander and Jaume Marti-Farre and Carles Padro},
      title = {On codes, matroids and secure multi-party computation from linear secret sharing schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2004/245},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/245}},
      url = {https://eprint.iacr.org/2004/245}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.