Paper 2011/375

Complexity of universal access structures

Laszlo Csirmaz

Abstract

An important parameter in a secret sharing scheme is the number of minimal qualified sets. Given this number, the universal access structure is the richest possible structure, namely the one in which there are one or more participants in every possible Boolean combination of the minimal qualified sets. Every access structure is a substructure of the universal structure for the same number of minimal qualified subsets, thus universal access structures have the highest complexity given the number of minimal qualified sets. We show that the complexity of the universal structure with $n$ minimal qualified sets is between $n/\log_2n$ and $n/2.7182\dots$ asymptotically.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
secret sharingcomplexityentropy method
Contact author(s)
csirmaz @ degas ceu hu
History
2011-07-12: received
Short URL
https://ia.cr/2011/375
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/375,
      author = {Laszlo Csirmaz},
      title = {Complexity of universal access structures},
      howpublished = {Cryptology ePrint Archive, Paper 2011/375},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/375}},
      url = {https://eprint.iacr.org/2011/375}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.