Cryptology ePrint Archive: Report 2016/194

How to Share a Secret, Infinitely

Ilan Komargodski and 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 where the size of the share each party gets is roughly $\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 advanced and could potentially be infinite. Our goal is to give the $t$-th party arriving a small share as possible as a function of $t$. Our main result is such a scheme for the $k$-threshold access structure 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}$.

Category / Keywords: foundations / Secret sharing, threshold access structure, dynamic access structures

Original Publication (with minor differences): IACR-TCC-2016

Date: received 23 Feb 2016, last revised 25 Aug 2016

Contact author: ilan komargodski at weizmann ac il

Available format(s): PDF | BibTeX Citation

Note: Added connection to prefix codes and simplified proof of Theorem 1.1

Version: 20160825:073744 (All versions of this report)

Short URL: ia.cr/2016/194

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]