New Monotone Span Programs from Old

Ventzislav Nikov; Svetla Nikova

Paper 2004/282 Original: eprint.iacr.org/2004/282 ↗

New Monotone Span Programs from Old

Ventzislav Nikov

Svetla Nikova

Abstract

In this paper we provide several known and one new constructions of new linear secret sharing schemes (LSSS) from existing ones. This constructions are well-suited for didactic purposes, which is a main goal of this paper. It is well known that LSSS are in one-to-one correspondence with monotone span programs (MSPs). MSPs introduced by Karchmer and Wigderson, can be viewed as a linear algebra model for computing a monotone function (access structure). Thus the focus is in obtaining a MSP computing the new access structure starting from the MSPs that compute the existing ones, in the way that the size of the MSP after the transformation is well defined. Next we define certain new operations on access structures and prove certain related properties.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2004-11-03: last updated; 2004-11-03: published
Short URL: https://ia.cr/2004/282
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2004/282,
      author = {Ventzislav Nikov and Svetla Nikova},
      title = {New Monotone Span Programs from Old},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/282},
      year = {2004},
      url = {https://eprint.iacr.org/2004/282}
}