International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Evolving Ramp Secret Sharing with a Small Gap

Authors:
Amos Beimel , Ben Gurion University, Beer Sheva, Israel
Hussien Othman , Ben Gurion University, Beer Sheva, Israel
Download:
DOI: 10.1007/978-3-030-45721-1_19 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
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: \NN\to \NN$ 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 $j$ 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{j}$, 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)$.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30238,
  title={Evolving Ramp Secret Sharing with a Small Gap},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Evolving Secret Sharing Schemes;Ramp Secret Sharing Schemes},
  volume={12105},
  doi={10.1007/978-3-030-45721-1_19},
  author={Amos Beimel and Hussien Othman},
  year=2020
}