Lower bounds for monotone span programs

DOI10.1007/BF01202040zbMath0870.68072OpenAlexW2169672310MaRDI QIDQ677989

Anna Gál, Amos Beimel, Mike S. Paterson

Publication date: 7 September 1997

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202040

zbMATH Keywords

span programslinear algebraic model of computationlinear secret-sharing schemes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Quadratic secret sharing and conditional disclosure of secrets, Secret-sharing schemes for very dense graphs, Optimal linear secret sharing schemes for graph access structures on six participants, Threshold Secret Sharing Requires a Linear Size Alphabet, Improving the linear programming technique in the search for lower bounds in secret sharing, On arithmetic branching programs, On Linear Secret Sharing for Connectivity in Directed Graphs, On the number of zero-patterns of a sequence of polynomials, Secret-Sharing Schemes: A Survey, Lower bounds for monotone span programs, An optimal multisecret threshold scheme construction, A note on monotone complexity and the rank of matrices, On abelian and homomorphic secret sharing schemes, Secret Sharing Schemes for Dense Forbidden Graphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the information rate of secret sharing schemes
• Lower bounds for monotone span programs
• On computing the determinant in small parallel time using a small number of processors
• The monotone circuit complexity of Boolean functions
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• On another Boolean matrix
• On the classification of ideal secret sharing schemes
• An explication of secret sharing schemes
• On the size of shares for secret sharing schemes
• Geometric secret sharing schemes and their duals
• On the information rate of perfect secret sharing schemes
• How to share a secret
• Structure and importance of logspace-MOD class
• On secret sharing systems
• Universally ideal secret-sharing schemes