Optimal Information Rate of Secret Sharing Schemes on Trees

DOI10.1109/TIT.2012.2236958zbMATH Open1364.94576arXiv1302.4609OpenAlexW1987772082MaRDI QIDQ2989337FDOQ2989337

Gábor Tardos, László Csirmaz

Publication date: 8 June 2017

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

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.

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)

Cited In (17)

• Optimal information ratio of secret sharing schemes on Dutch windmill graphs
• Ideal secret sharing schemes on graph-based $3$-homogeneous access structures
• Title not available (Why is that?)
• Exact information ratios for secret sharing on small graphs with girth at least 5
• On the information ratio of non-perfect secret sharing schemes
• On the information ratio of graphs without high-degree neighbors
• Secret-sharing schemes for very dense graphs
• Secret sharing on large girth graphs
• Improving the linear programming technique in the search for lower bounds in secret sharing
• Reduced access structures with four minimal qualified subsets on six participants
• Secret sharing on the \(d\)-dimensional cube
• The optimal average information ratio of secret-sharing schemes for the access structures based on unicycle graphs and bipartite graphs
• Optimal linear secret sharing schemes for graph access structures on six participants
• Succinct computational secret sharing
• Secret Sharing Schemes for (k, n)-Consecutive Access Structures
• Secret sharing on regular bipartite access structures
• 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)