Complexity of universal access structures

DOI10.1016/J.IPL.2011.10.022MaRDI QIDQ413265zbMATH OpenOpenAlexFDO

Authors László Csirmaz

Publication date 4 May 2012

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

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)

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.

Recommendations

• Universally ideal secret-sharing schemes
• The complexity of the connected graph access structure on seven participants
• Optimal complexity of secret sharing schemes with four minimal qualified subsets
• On the size of shares for secret sharing schemes
• scientific article; zbMATH DE number 2108154

Cites work

• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• An impossibility result on graph secret sharing
• Decomposition constructions for secret-sharing schemes
• Optimal complexity of secret sharing schemes with four minimal qualified subsets
• Secret sharing schemes with three or four minimal qualified subsets
• Tight bounds on the information rate of secret sharing schemes

Cited in

(7)

• The complexity of the graph access structures on six participants
• Optimal complexity of secret sharing schemes with four minimal qualified subsets
• Access structures determined by uniform polymatroids
• Average complexities of access structures on five participants
• The complexity of the connected graph access structure on seven participants
• The accessibility of an access structure
• Quantum attribute-based encryption: a comprehensive study

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)