On the size of monotone span programs

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (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.
Originele taal-2Engels
TitelSecurity in Communication Networks (4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Revised Selected Papers)
RedacteurenC. Blundo, S. Cimato
Plaats van productieBerlin
ISBN van geprinte versie3-540-24301-1
StatusGepubliceerd - 2005

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'On the size of monotone span programs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit