Paper 2005/376

Representing small identically self-dual matroids by self-dual codes

Carles Padro and Ignacio Gracia

Abstract

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.

Note: 24 Oct 2005: Minor revision. Some little mistakes corrected. 5 Jan 2007: Publication Info updated

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is a preliminary version of the paper that appeared in Siam Journal on Discrete Mathematics
Keywords
secret sharingmultiplicative secret sharing schemessecure multi-party computationidentically self-dual matroidsself-dual codes
Contact author(s)
matcpl @ ma4 upc edu
History
2007-01-05: last of 2 revisions
2005-10-23: received
See all versions
Short URL
https://ia.cr/2005/376
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/376,
      author = {Carles Padro and Ignacio Gracia},
      title = {Representing small identically self-dual matroids by self-dual codes},
      howpublished = {Cryptology ePrint Archive, Paper 2005/376},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/376}},
      url = {https://eprint.iacr.org/2005/376}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.