On the size of monotone span programs

V.S. Nikov, S.I. Nikova, B. Preneel

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


Span programs provide a linear algebraic model of computation. Monotone span programs (MSP) correspond to linear secret sharing schemes. This paper studies the properties of monotone span programs related to their size. Using the results of van Dijk (connecting codes and MSPs) and a construction for a dual monotone span program proposed by Cramer and Fehr we prove a non-trivial upper bound for the size of monotone span programs. By combining the concept of critical families with the dual monotone span program construction of Cramer and Fehr we improve the known lower bound with a constant factor, showing that the lower bound for the size of monotone span programs should be approximately twice as large. Finally, we extend the result of van Dijk showing that for any MSP there exists a dual MSP such that the corresponding codes are dual.
Original languageEnglish
Title of host publicationSecurity in Communication Networks (4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Revised Selected Papers)
EditorsC. Blundo, S. Cimato
Place of PublicationBerlin
ISBN (Print)3-540-24301-1
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'On the size of monotone span programs'. Together they form a unique fingerprint.

Cite this