Evolving Ramp Secret Sharing with a Small Gap

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 ->. 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 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 (O) over tilde (j(4-1/log2 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 root j, in which the share size of the j-th party is (O) over tilde (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 (O) over tilde (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).