IACR paper details
Title  Secret sharing on infinite graphs 

Booktitle  IACR Eprint archive 

Pages  

Year  2007 

URL  http://eprint.iacr.org/2007/297 

Author  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, twodimensional 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.


Search for the paper
@misc{eprint200713577,
title={Secret sharing on infinite graphs},
booktitle={IACR Eprint archive},
keywords={foundations / Secret sharing scheme, information},
url={http://eprint.iacr.org/2007/297},
note={Submitted to Tatra Mountains Mathematical Publications csirmaz@renyi.hu 13726 received 1 Aug 2007},
author={Laszlo Csirmaz},
year=2007
}
Download a complete BibTeX file.