Evolving Secret Sharing Schemes Based on Polynomial Evaluations and Algebraic Geometry Codes
Chaoping Xing, Chen Yuan · IEEE Transactions on Information Theory · 2024
A secret sharing scheme enables the dealer to share a secret amongnparties. A classic secret sharing scheme takes the numbernof parties and the secret as the input. Ifnis not known in advance, the classic secret sharing scheme may fail. Komargodski, Naor, and Yogev [8] first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work [8], [9], and [2], evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in [2] are inspired by the scheme given in [8], namely, these schemes rely on 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 sizek1+ϵlogtfor any constant ϵ > 0. Thus, our scheme achieves almost the same share size as in [8]. Moreover, our scheme is obtained by a direct construction while the scheme in [8] that achieves the (k- 1) logtshare size is obtained by a recursive construction, which makes their structure complicated. Our second scheme is an evolvingkt-threshold secret sharing scheme with any sequence {kt}∞t=1of threshold values that has share sizet4. This scheme improves the share size by logtgiven in [9], where a dynamic evolvingkt-threshold secret sharing scheme with the share sizeO(t4logt) was proposed. In addition, we also show that if the threshold valuesktgrow in rate ⌊tβ⌋ for a real β ∈ (0, 1), then we have a dynamic evolving threshold secret sharing scheme with the share sizeO(t4β). Our last scheme is an evolving (αt, βt)-ramp secret sharing scheme with constant share size for some α, β. 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 in [9] can also transform all of our schemes to a robust scheme as our scheme is linear.