Secret sharing on large girth graphs

DOI10.1007/S12095-018-0338-XzbMATH Open1412.94166arXiv1705.10520OpenAlexW2964081642MaRDI QIDQ2632835FDOQ2632835

Péter Ligeti, László Csirmaz

Publication date: 15 May 2019

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

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.

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

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

zbMATH Keywords

information ratiogirthsecret sharing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Exact information ratios for secret sharing on small graphs with girth at least 5
• 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)