<abstract xmlns="http://www.w3.org/1999/xhtml">We investigate the information ratio of graph-based secret sharing schemes. This ratio characterizes the efficiency of a scheme measured by the amount of information the participants must remember for each bits in the secret.We examine the information ratio of several systems based on graphs with many leaves, by proving non-trivial lower and upper bounds for the ratio. On one hand, we apply the so-called entropy method for proving that the lower bound for the information ratio of <italic>n</italic>-sunlet graphs composed of a 1-factor between the vertices of a cycle <italic>Cn</italic> and <italic>n</italic> independent vertices is 2. On the other hand, some symmetric and recursive constructions are given that yield the upper bounds. In particular, we show that the information ratio of every graph composed of a 1-factor between a complete graph <italic>Kn</italic> and at most 4 independent vertices is smaller than 2.</abstract>

We investigate the information ratio of graph-based secret sharing schemes. This ratio characterizes the efficiency of a scheme measured by the amount of information the participants must remember for each bits in the secret.We examine the information ratio of several systems based on graphs with many leaves, by proving non-trivial lower and upper bounds for the ratio. On one hand, we apply the so-called entropy method for proving that the lower bound for the information ratio of n-sunlet graphs composed of a 1-factor between the vertices of a cycle Cn and n independent vertices is 2. On the other hand, some symmetric and recursive constructions are given that yield the upper bounds. In particular, we show that the information ratio of every graph composed of a 1-factor between a complete graph Kn and at most 4 independent vertices is smaller than 2.

On the Information Ratio of Graphs with Many Leaves

3in Research Group, Faculty of Informatics

Tatra Mountains Mathematical Publications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"On the Information Ratio of Graphs with Many Leaves"}

We investigate the information ratio of graph-based secret sharing schemes. This ratio characterizes the efficiency of a scheme measured by the amount of...

On the Information Ratio of Graphs with Many Leaves

Published Online: Aug 15, 2019

Page range: 97 - 108

Received: Aug 31, 2018

DOI: https://doi.org/10.2478/tmmp-2019-0008

Keywords
secret sharing, information ratio, entropy method

© 2019 Máté Gyarmati et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

On the Information Ratio of Graphs with Many Leaves

Published Online: Aug 15, 2019

Page range: 97 - 108

Received: Aug 31, 2018

DOI: https://doi.org/10.2478/tmmp-2019-0008

Keywordssecret sharing, information ratio, entropy method

© 2019 Máté Gyarmati et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
secret sharing, information ratio, entropy method