Exact information ratios for secret sharing on small graphs with girth at least 5
Autor: | Péter Ligeti, Károly Harsányi |
---|---|
Rok vydání: | 2019 |
Předmět: |
Computer science
Applied Mathematics 05c6 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Girth (graph theory) 01 natural sciences Secret sharing Computer Science Applications Combinatorics Computational Mathematics Information ratio 010201 computation theory & mathematics information ratio graph covering secret sharing QA1-939 0202 electrical engineering electronic engineering information engineering 94a60 Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
Zdroj: | Journal of Mathematical Cryptology, Vol 13, Iss 2, Pp 107-116 (2019) |
ISSN: | 1862-2984 1862-2976 |
Popis: | In a secret-sharing scheme, a piece of information – the secret – is distributed among a finite set of participants in such a way that only some predefined coalitions can recover it. The efficiency of the scheme is measured by the amount of information the most heavily loaded participant must remember. This amount is called information ratio, and one of the most interesting problems of this topic is to calculate the exact information ratio of given structures. In this paper, the information ratios of all but one graph-based schemes on 8 or 9 vertices with a girth at least 5 and all graph-based schemes on 10 vertices and 10 edges with a girth at least 5 are determined using two polyhedral combinatoric tools: the entropy method and covering with stars. Beyond the investigation of new graphs, the paper contains a few improvements and corrections of recent results on graphs with 9 vertices. Furthermore, we determine the exact information ratio of a large class of generalized sunlet graphs consisting of some pendant paths attached to a cycle of length at least 5. |
Databáze: | OpenAIRE |
Externí odkaz: |