Paper 2019/1124
Evolving Ramp Secret Sharing with a Small Gap
Amos Beimel and Hussien Othman
Abstract
Evolving secretsharing schemes, introduced by Komargodski, Naor, and Yogev (TCC 2016b), are secretsharing schemes in which there is no apriory upper bound on the number of parties that will participate. The parties arrive one by one and when a party arrives the dealer gives it a share; the dealer cannot update this share when other parties arrive. Motivated by the fact that when the number of parties is known, ramp secretsharing schemes are more efficient than threshold secretsharing schemes, we study evolving ramp secretsharing schemes. Specifically, we study evolving $(b(j),g(j))$ramp secretsharing schemes, where $g,b: N \to N$ are nondecreasing functions. In such schemes, any set of parties that for some $j$ contains $g(j)$ parties from the first parties that arrive can reconstruct the secret, and any set such that for every $j$ contains less than $b(j)$ parties from the first parties that arrive cannot learn any information about the secret. We focus on the case that the gap is small, namely $g(j)b(j)=j^{\beta}$ for $0<\beta<1$. We show that there is an evolving ramp secretsharing scheme with gap $t^{\beta}$, in which the share size of the $j$th party is $\tilde{O}(j^{4\frac{1}{\log^2 {1/\beta}}})$. Furthermore, we show that our construction results in much better share size for fixed values of $\beta$, i.e., there is an evolving ramp secretsharing scheme with gap $\sqrt{t}$, in which the share size of the $j$th party is $\tilde{O}(j)$. Our construction should be compared to the best known evolving $g(j)$threshold secretsharing schemes (i.e., when $b(j)=g(j)1$) in which the share size of the $j$th party is $\tilde{O}(j^4)$. Thus, our construction offers a significant improvement for every constant $\beta$, showing that allowing a gap between the sizes of the authorized and unauthorized sets can reduce the share size. In addition, we present an evolving $(k/2,k)$ramp secretsharing scheme for a constant $k$ (which can be very big), where any set of parties of size at least $k$ can reconstruct the secret and any set of parties of size at most $k/2$ cannot learn any information about the secret. The share size of the $j$th party in our construction is $O(\log k\log j)$. This is an improvement over the best known evolving $k$threshold secretsharing schemes in which the share size of the $j$th party is $O(k\log j)$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published by the IACR in EUROCRYPT 2020
 Keywords
 secret sharing
 Contact author(s)

amos beimel @ gmail com
hussien othman @ gmail com  History
 20200221: revised
 20191002: received
 See all versions
 Short URL
 https://ia.cr/2019/1124
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1124, author = {Amos Beimel and Hussien Othman}, title = {Evolving Ramp Secret Sharing with a Small Gap}, howpublished = {Cryptology ePrint Archive, Paper 2019/1124}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/1124}}, url = {https://eprint.iacr.org/2019/1124} }