Complexity of universal access structures

DOI10.1016/J.IPL.2011.10.022zbMATH Open1277.94050arXiv1908.05021OpenAlexW1987871737MaRDI QIDQ413265FDOQ413265

László Csirmaz

Publication date: 4 May 2012

Published in: Information Processing Letters (Search for Journal in Brave)

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/lo{g}_{2}n$ and $n/2.7182$ asymptotically.

Full work available at URL: https://arxiv.org/abs/1908.05021

zbMATH Keywords

complexityharmonic seriescryptographyentropy methodsecret-sharing

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• Title not available (Why is that?)
• Decomposition constructions for secret-sharing schemes
• An impossibility result on graph secret sharing
• Tight bounds on the information rate of secret sharing schemes
• Secret sharing schemes with three or four minimal qualified subsets
• Optimal complexity of secret sharing schemes with four minimal qualified subsets

Cited In (2)

• Quantum attribute-based encryption: a comprehensive study
• Access structures determined by uniform polymatroids

This page was built for publication: Complexity of universal access structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q413265)