Paper 2012/412

Probabilistic Infinite Secret Sharing

Laszlo Csirmaz

Abstract

The study of probabilistic secret sharing schemes using arbitrary probability spaces and possibly infinite number of participants lets us investigate abstract properties of such schemes. It highlights important properties, explains why certain definitions work better than others, connects this topic to other branches of mathematics, and might yield new design paradigms. A {\em probabilistic secret sharing scheme} is a joint probability distribution of the shares and the secret together with a collection of {\em secret recovery functions} for qualified subsets. The scheme is measurable if the recovery functions are measurable. Depending on how much information an unqualified subset might have, we define four scheme types: {\em perfect}, {\em almost perfect}, {\em ramp}, and {\em almost ramp}. Our main results characterize the access structures which can be realized by schemes of these types. We show that every access structure can be realized by a non-measurable perfect probabilistic scheme. The construction is based on a paradoxical pair of independent random variables which determine each other. For measurable schemes we have the following complete characterization. An access structure can be realized by a (measurable) perfect, or almost perfect scheme if and only if the access structure, as a subset of the Sierpiński space $\{0,1\}^P$, is open, if and only if it can be realized by a span program. The access structure can be realized by a (measurable) ramp or almost ramp scheme if and only if the access structure is a $G_\delta$ set (intersection of countably many open sets) in the Sierpiński topology, if and only if it can be realized by a Hilbert-space program.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
secret sharing
Contact author(s)
csirmaz @ degas ceu hu
History
2012-07-25: received
Short URL
https://ia.cr/2012/412
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/412,
      author = {Laszlo Csirmaz},
      title = {Probabilistic Infinite Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2012/412},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/412}},
      url = {https://eprint.iacr.org/2012/412}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.