You are looking at a specific version 20070807:154231 of this paper. See the latest version.

Paper 2007/297

Secret sharing on infinite graphs

Laszlo Csirmaz

Abstract

We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) {\it information ratio} of an access structure is the largest lower bound on the amount of information some participant must remember for each bit in the secret -- just the inverse of the information rate. We determine this value for several infinite graphs: infinite path, two-dimensional square and honeycomb lattices; and give upper and lower bounds on the ratio for the triangular lattice. It is also shown that the information ratio is not necessarily {\em local}, i.e.~all finite spanned subgraphs have strictly smaller ratio than the whole graph. We conclude the paper by posing several open problems.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Submitted to Tatra Mountains Mathematical Publications
Keywords
Secret sharing schemeinformation
Contact author(s)
csirmaz @ renyi hu
History
2007-08-07: received
Short URL
https://ia.cr/2007/297
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.