Paper 2019/1124

Evolving Ramp Secret Sharing with a Small Gap

Amos Beimel and 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 $$ contains less than $$ 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 $$ for $$. We show that there is an evolving ramp secret-sharing scheme with gap $$, in which the share size of the $$-th party is $$. Furthermore, we show that our construction results in much better share size for fixed values of $$, i.e., there is an evolving ramp secret-sharing scheme with gap $$, in which the share size of the $$-th party is $$. Our construction should be compared to the best known evolving $$-threshold secret-sharing schemes (i.e., when $$) in which the share size of the $$-th party is $$. Thus, our construction offers a significant improvement for every constant $$, 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 $$-ramp secret-sharing scheme for a constant $$ (which can be very big), where any set of parties of size at least $$ can reconstruct the secret and any set of parties of size at most $$ cannot learn any information about the secret. The share size of the $$-th party in our construction is $$. This is an improvement over the best known evolving $$-threshold secret-sharing schemes in which the share size of the $$-th party is $$.