Secret sharing on large girth graphs

DOI10.1007/S12095-018-0338-XMaRDI QIDQ2632835zbMATH OpenOpenAlexFDO

Authors László Csirmaz, Péter Ligeti

Publication date 15 May 2019

Published in Cryptography and Communications (Search for Journal in Brave)

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

zbMATH Keywords

information ratiogirthsecret sharing

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Cryptography (94A60)

Abstract: We investigate graph based secret sharing schemes and its information ratio, also called complexity, measuring the maximal amount of information the vertices has to store. It was conjectured that in large girth graphs, where the interaction between far away nodes is restricted to a single path, this ratio is bounded. This conjecture was supported by several result, most notably by a result of Csirmaz and Ligeti saying that the complexity of graphs with girth at least six and no neighboring high degree vertices is strictly below 2. In this paper we refute the above conjecture. First, a family of $d$-regular graphs is defined iteratively such that the complexity of these graphs is the largest possible $(d+1)/2$ allowed by Stinson's bound. This part extends earlier results of van Dijk and Blundo et al, and uses the so-called entropy method. Second, using combinatorial arguments, we show that this family contains graphs with arbitrary large girth. In particular, we obtain the following purely combinatorial result, which might be interesting on its own: there are $d$-regular graphs with arbitrary large girth such that any fractional edge-cover by stars (or by complete multipartite graphs) must cover some vertex $(d+1)/2$ times.

Recommendations

• On an infinite family of graphs with information ratio \(2 - 1/k\)
• Exact information ratios for secret sharing on small graphs with girth at least 5
• Graph decompositions and secret sharing schemes
• On the information ratio of graphs without high-degree neighbors
• An impossibility result on graph secret sharing

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• Covering a graph by complete bipartite graphs
• Decomposition constructions for secret-sharing schemes
• Erdős-Pyber theorem for hypergraphs and secret sharing
• Graph decompositions and secret sharing schemes
• On an infinite family of graphs with information ratio \(2 - 1/k\)
• On the information rate of perfect secret sharing schemes
• Optimal Information Rate of Secret Sharing Schemes on Trees
• Secret sharing schemes on graphs
• Secret-Sharing Schemes: A Survey
• Some improved bounds on the information rate of perfect secret sharing schemes
• The size of a share must be large
• Tight bounds on the information rate of secret sharing schemes

Cited in

(3)

• Exact information ratios for secret sharing on small graphs with girth at least 5
• On the information ratio of graphs without high-degree neighbors
• Percolation in the secrecy graph

This page was built for publication: Secret sharing on large girth graphs

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