Optimal Information Rate of Secret Sharing Schemes on Trees

DOI10.1109/TIT.2012.2236958MaRDI QIDQ2989337zbMATH OpenOpenAlexFDO

Authors László Csirmaz, Gábor Tardos

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Authentication, digital signatures and secret sharing (94A62)

Abstract: The information rate for an access structure is the reciprocal of the load of the optimal secret sharing scheme for this structure. We determine this value for all trees: it is 1/(2-1/c), where c is the size of the largest core of the tree. A subset of the vertices of a tree is a core if it induces a connected subgraph and for each vertex in the subset one finds a neighbor outside the subset. Our result follows from a lower and an upper bound on the information rate that applies for any graph and happen to coincide for trees because of a correspondence between the size of the largest core and a quantity related to a fractional cover of the tree with stars.

Cited in

(17)

• On the information ratio of graphs without high-degree neighbors
• Exact information ratios for secret sharing on small graphs with girth at least 5
• Secret sharing on large girth graphs
• Succinct computational secret sharing
• Optimal linear secret sharing schemes for graph access structures on six participants
• Optimal information ratio of secret sharing schemes on Dutch windmill graphs
• Secret Sharing Schemes for (k, n)-Consecutive Access Structures
• Secret sharing on the \(d\)-dimensional cube
• Improving the linear programming technique in the search for lower bounds in secret sharing
• The optimal average information ratio of secret-sharing schemes for the access structures based on unicycle graphs and bipartite graphs
• Secret sharing on regular bipartite access structures
• Threshold secret sharing requires a linear-size alphabet
• Ideal secret sharing schemes on graph-based 3-homogeneous access structures
• On the information ratio of non-perfect secret sharing schemes
• Reduced access structures with four minimal qualified subsets on six participants
• Secret-sharing schemes for very dense graphs
• Bipartite secret sharing and staircases

This page was built for publication: Optimal Information Rate of Secret Sharing Schemes on Trees

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