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.
Category / Keywords: cryptographic protocols / secret sharing, multiplicative secret sharing schemes, secure multi-party computation, identically self-dual matroids, self-dual codes Publication Info: This is a preliminary version of the paper that appeared in Siam Journal on Discrete Mathematics Date: received 19 Oct 2005, last revised 5 Jan 2007 Contact author: matcpl at ma4 upc edu Available format(s): PDF | BibTeX Citation Note: 24 Oct 2005: Minor revision. Some little mistakes corrected. 5 Jan 2007: Publication Info updated Version: 20070105:133959 (All versions of this report) Short URL: ia.cr/2005/376 Discussion forum: Show discussion | Start new discussion