Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR16-023 | 25th August 2016 09:34

How to Share a Secret, Infinitely

RSS-Feed




Revision #3
Authors: Ilan Komargodski, Moni Naor, Eylon Yogev
Accepted on: 25th August 2016 09:34
Downloads: 256
Keywords: 


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 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 where the share size of party $t$ is $(k-1)\cdot \log t + 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}$.


Revision #2 to TR16-023 | 22nd March 2016 15:33

How to Share a Secret, Infinitely





Revision #2
Authors: Ilan Komargodski, Moni Naor, Eylon Yogev
Accepted on: 22nd March 2016 15:33
Downloads: 298
Keywords: 


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 + 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}$.



Changes to previous version:

Added connection to prefix codes and simplified proof of Theorem 1.1


Revision #1 to TR16-023 | 24th February 2016 09:03

How to Share a Secret, Infinitely





Revision #1
Authors: Ilan Komargodski, Moni Naor, Eylon Yogev
Accepted on: 24th February 2016 09:03
Downloads: 232
Keywords: 


Abstract:

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best known access structure is the $k$-threshold one, where any subset of size $k$ or more is qualified and all smaller subsets are not qualified. A major issue is the size of the shares needed to assure this property. For the threshold access structure, when $k=2$ and there are $n$ parties it is known that the share size must be $\log n$ even for secrets of 1 bit.

In this work we consider the case where the set of parties is not known in advanced and could potentially be infinite. We would still like to give the $t$-th party arriving a small share as possible as a function of $t$. We show that for any access structure it is possible to do so by giving shares of size $2^{t-1}$. Our main result is a scheme for $k$-threshold access structure with shares of size $(k-1)\cdot \log t + {poly}(k)\cdot o(\log t)$ bits. Finally, we prove that no secret sharing scheme for the 2-threshold access structure with share size at most $\log{t} + \log\log t + O(1)$ exists.


Paper:

TR16-023 | 23rd February 2016 21:32

How to Share a Secret, Infinitely





TR16-023
Authors: Ilan Komargodski, Moni Naor, Eylon Yogev
Publication: 23rd February 2016 22:16
Downloads: 320
Keywords: 


Abstract:

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best known access structure is the $k$-threshold one, where any subset of size $k$ or more is qualified and all smaller subsets are not qualified. A major issue is the size of the shares needed to assure this property. For the threshold access structure, when $k=2$ and there are $n$ parties it is known that the share size must be $\log n$ even for secrets of 1 bit.

In this work we consider the case where the set of parties is not known in advanced and could potentially be infinite. We would still like to give the $t$-th party arriving a small share as possible as a function of $t$. We show that for any access structure it is possible to do so by giving shares of size $2^{t-1}$. Our main result is a scheme for $k$-threshold access structure with shares of size $(k-1)\cdot \log t + {poly}(k)\cdot o(\log t)$ bits. Finally, we prove that no secret sharing scheme for the 2-threshold access structure with share size at most $\log{t} + \log\log t + O(1)$ exists.



ISSN 1433-8092 | Imprint