International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Carles PadrĂ³
Ignacio Gracia
Download:
URL: http://eprint.iacr.org/2005/376
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12710,
  title={Representing small identically self-dual matroids by self-dual codes},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / secret sharing, multiplicative secret sharing schemes, secure multi-party computation, identically self-dual matroids, self-dual codes},
  url={http://eprint.iacr.org/2005/376},
  note={This is a preliminary version of the paper that appeared in Siam Journal on Discrete Mathematics matcpl@ma4.upc.edu 13518 received 19 Oct 2005, last revised 5 Jan 2007},
  author={Carles PadrĂ³ and Ignacio Gracia},
  year=2005
}