Welcome to the resource topic for 2019/1124
Title:
Evolving Ramp Secret Sharing with a Small Gap
Authors: Amos Beimel, Hussien Othman
Abstract:Evolving secret-sharing schemes, introduced by Komargodski, Naor, and Yogev (TCC 2016b), are secret-sharing schemes in which there is no a-priory 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 secret-sharing schemes are more efficient than threshold secret-sharing schemes, we study evolving ramp secret-sharing schemes. Specifically, we study evolving (b(j),g(j))-ramp secret-sharing schemes, where g,b: N \to N are non-decreasing 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 secret-sharing 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 secret-sharing 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 secret-sharing 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 secret-sharing 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 secret-sharing schemes in which the share size of the j-th party is O(k\log j).
ePrint: https://eprint.iacr.org/2019/1124
Talk: https://www.youtube.com/watch?v=OaM4nvc5itg
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .