Welcome to the UPF Digital Repository

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

Show simple item record

dc.contributor.author Cramer, Ronald
dc.contributor.author Daza, Vanesa
dc.contributor.author Gracia, Ignacio
dc.contributor.author Jiménez Urroz, Jorge
dc.contributor.author Leander, Gregor
dc.contributor.author Martí, Jaume, 1943-
dc.contributor.author Padró, Carles
dc.date.accessioned 2013-02-27T15:44:58Z
dc.date.available 2013-02-27T15:44:58Z
dc.date.issued 2008
dc.identifier.citation Cramer R, Daza V, Gracia I, Jiménez-Urroz J, Leander G, Martí-Farré J et al. On codes, matroids, and secure multiparty computation from linear secret-sharing schemes. IEEE Trans. Inf. Theory. 2008; 54(6): 2644-2657. DOI 10.1109/TIT.2008.921692
dc.identifier.issn 0018-9448
dc.identifier.uri http://hdl.handle.net/10230/20429
dc.description.abstract Error-correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, the connections between codes, matroids, and a special class of secret sharing schemes, namely, multiplicative linear secret sharing schemes (LSSSs), are studied. Such schemes are known to enable multiparty computation protocols secure against general (nonthreshold) adversaries./nTwo 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. A property of strongly multiplicative LSSSs that could be useful in solving this problem is proved. Namely, using a suitable generalization of the well-known Berlekamp–Welch decoder, it is shown 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, the considered open problem is to determine 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 restated in terms of representability of identically self-dual matroids by self-dual codes. A new concept is introduced, 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. It is proved 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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Institute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartof IEEE Transactions on Information Theory. 2008; 54(6)
dc.rights © 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works./nThe final published article can be found at http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4529268
dc.subject.other Criptografia
dc.subject.other Seguretat informàtica
dc.title On codes, matroids, and secure multiparty computation from linear secret-sharing schemes
dc.type info:eu-repo/semantics/article
dc.identifier.doi http://dx.doi.org/10.1109/TIT.2008.921692
dc.subject.keyword Efficient error correction
dc.subject.keyword Multiparty computation
dc.subject.keyword Multiplicative linear secret sharing schemes
dc.subject.keyword Self-dual codes
dc.subject.keyword Self-dual matroids
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/publishedVersion

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


Compliant to Partaking