Evolving Secret Sharing Schemes Based on Polynomial Evaluations and Algebraic Geometry Codes

A secret sharing scheme enables the dealer to share a secret among n parties. A classic secret sharing scheme takes the number n of parties and the secret as the input. If n is not known in advance, the classic secret sharing scheme may fail. Komargodski et al. (2016) first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work Beimel and Othman (2020), Komargodski et al. (2016), and Komargodski and Paskin-Cherniavsky (2017), evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction by Beimel and Othman (2020) are inspired by the scheme given by Komargodski et al. (2016), namely, these schemes relyon the scheme for st-connectivity which allows to generate infinite number of shares. In this work, we revisit evolving secret sharing schemes and present three constructions that take completely different approach. Our first scheme is an evolvingk-threshold secret sharing scheme with share size k(1+epsilon) log t for any constant epsilon > 0. Thus, our scheme achieves almost the same share size as by Komargodski et al. (2016). Moreover, our scheme is obtained by a direct construction while the scheme by Komargodski et al.(2016) that achieves the (k-1) logtshare size is obtained by are cursive construction, which makes their structure complicated. Our second scheme is an evolving k-threshold secret sharing scheme with any sequence{k(t)}(t=1)(infinity) of threshold values that has share size t(4). This scheme improves the share size by log t given by Komargodski and Paskin-Cherniavsky (2017), where adynamic evolving k-threshold secret sharing scheme with the share size O(t(4) log t) was proposed. In addition, we also show that if the threshold values k(t) grow in rate [t(beta)] for a real beta is an element of(0,1), then we have a dynamic evolving threshold secret sharing scheme with the share size O(t(4 beta)). Our last scheme is an evolving(alpha t ,beta t)-ramp secret sharing scheme with constant share size for some alpha, beta. One major feature of this ramp scheme is that it is multiplicative as the scheme is also an arithmetic secret sharing scheme. We note that the same technique by Komargodski and Paskin-Cherniavsky (2017) can also transform all of our schemes to a robust scheme as our scheme is linear.