Separating the Power of Monotone Span Programs over Different Fields

DOI10.1137/S0097539704444038MaRDI QIDQ5317192zbMATH OpenFDO

Authors Amos Beimel, Enav Weinreb

Publication date 16 September 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539704444038

zbMATH Keywords

algebraic models of computationlower boundsmonotone span programssecret sharing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algebraic theory of languages and automata (68Q70) Combinatorics in computer science (68R05) Authentication, digital signatures and secret sharing (94A62)

Recommendations

• Lifting Nullstellensatz to monotone span programs over any field
• Security in Communication Networks
• Lower bounds for monotone span programs
• Superpolynomial lower bounds for monotone span programs
• An efficient construction of dual monotone span programs

Cited in

(19)

• An impossibility result on graph secret sharing
• A characterization of span program size and improved lower bounds for monotone span programs
• Finding lower bounds on the complexity of secret sharing schemes by linear programming
• Superpolynomial lower bounds for monotone span programs
• On abelian and homomorphic secret sharing schemes
• Extending Brickell-Davenport theorem to non-perfect secret sharing schemes
• An efficient construction of dual monotone span programs
• Secret-Sharing Schemes: A Survey
• Ideal secret sharing schemes for useful multipartite access structures
• On secret sharing schemes, matroids and polymatroids
• On Linear Secret Sharing for Connectivity in Directed Graphs
• Construction of a monotone span program with multiplication
• Threshold secret sharing requires a linear-size alphabet
• Lifting Nullstellensatz to monotone span programs over any field
• Security in Communication Networks
• Lower bounds for monotone span programs
• New method to compute bounds on the optimal information rate of secret sharing schemes
• Optimal complexity of secret sharing schemes with four minimal qualified subsets
• On the optimization of bipartite secret sharing schemes

This page was built for publication: Separating the Power of Monotone Span Programs over Different Fields

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