Paper 2016/194

How to Share a Secret, Infinitely

Ilan Komargodski, Moni Naor, and Eylon Yogev

Abstract

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the $k$-threshold access structure, where the qualified subsets are those of size at least $k$. When $k=2$ and there are $n$ parties, there are schemes for sharing an $\ell$-bit secret in which the share size of each party is roughly $\max\{\ell,\log n\}$ bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties $n$ must be given in advance to the dealer. In this work we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the $t$-th party arriving the smallest possible share as a function of $t$. Our main result is such a scheme for the $k$-threshold access structure and 1-bit secrets where the share size of party $t$ is $(k-1)\cdot \log t + \mathsf{poly}(k)\cdot o(\log t)$. For $k=2$ we observe an equivalence to prefix codes and present matching upper and lower bounds of the form $\log t + \log\log t + \log\log\log t + O(1)$. Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size $2^{t-1}$.

Note: IEEE Transactions on Information Theory; doi 10.1109/TIT.2017.2779121

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
dynamic access structuresecret sharingthreshold access structure
Contact author(s)
komargodski @ cornell edu
eylon yogev @ weizmann ac il
History
2018-05-08: last of 3 revisions
2016-02-24: received
See all versions
Short URL
https://ia.cr/2016/194
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/194,
      author = {Ilan Komargodski and Moni Naor and Eylon Yogev},
      title = {How to Share a Secret, Infinitely},
      howpublished = {Cryptology ePrint Archive, Paper 2016/194},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/194}},
      url = {https://eprint.iacr.org/2016/194}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.