Secret-sharing matroids need not be algebraic

DOI10.1016/J.DISC.2016.02.012zbMATH Open1337.05016arXiv1403.6363OpenAlexW2345183660MaRDI QIDQ284751FDOQ284751

Aner Ben-Efraim

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We combine some known results and techniques with new ones to show that there exists a non-algebraic, multi-linear matroid. This answers an open question by Matus (Discrete Mathematics 1999), and an open question by Pendavingh and van Zwam (Advances in Applied Mathematics 2013). The proof is constructive and the matroid is explicitly given.

Full work available at URL: https://arxiv.org/abs/1403.6363

Recommendations

• On secret-sharing matroids
• On Matroids and Nonideal Secret Sharing
• Matroids Can Be Far from Ideal Secret Sharing
• On secret sharing schemes, matroids and polymatroids
• Theory of Cryptography

zbMATH Keywords

algebraic matroidsmulti-linear matroids

Mathematics Subject Classification ID

Theory of matrix inversion and generalized inverses (15A09) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A class of geometric lattices based on finite groups
• Algebraic characteristic sets of matroids
• On the classification of ideal secret sharing schemes
• On secret-sharing matroids
• Matroid representations by partitions
• Almost affine codes
• Skew partial fields, multilinear representations of matroids, and a matrix tree theorem
• Dowling geometries representable over rings
• Title not available (Why is that?)
• Non‐Algebraic Matroids exist
• On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-linear Secret-Sharing Schemes
• Matroids algebraic over F(t) are algebraic over F

Cited In (8)

• On Secret Sharing Schemes, Matroids and Polymatroids
• A note on representing dowling geometries by partitions
• Secret sharing schemes for ports of matroids of rank 3
• Classes of matroids closed under minors and principal extensions
• Common information, matroid representation, and secret sharing for matroid ports
• Algebraic matroids and Frobenius flocks
• Algebraic matroids are almost entropic
• Representability of matroids by \(c\)-arrangements is undecidable

This page was built for publication: Secret-sharing matroids need not be algebraic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284751)