Paper 2021/1115

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

Chaoping Xing and Chen Yuan

Abstract

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, Naor, and Yogev \cite[TCC 2016]{KNY16} first proposed the evolving secret sharing scheme that only takes the secret as the input. In the work \cite[TCC 2016]{KNY16}, \cite[TCC 2017]{KC17} and \cite[Eurocrypt 2020]{BO20}, evolving threshold and ramp secret sharing schemes were extensively investigated. However, all of their constructions except for the first construction in \cite{BO20} are inspired by the scheme given in \cite{KNY16}, 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. Most of the previous schemes mentioned above have more combinatorial flavor, while our schemes are more algebraic in nature. More precisely speaking, our evolving secret sharing schemes are obtained via either the Shamir secret sharing or arithmetic secret sharing from algebraic geometry codes alone. Our first scheme is an evolving $k$-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 in \cite[TCC 2016]{KNY16}. Moreover, our scheme is obtained by a direct construction while the scheme in \cite[TCC 2016]{KNY16} that achieves the $(k-1)\log t$ share size is obtained by a recursive construction which makes their structure complicated. Our second scheme is an evolving $k_t$-threshold secret sharing scheme with any sequence $\{k_t\}_{t=1}^\infty$ of threshold values that has share size $t^4$. This scheme improves the share size by $\log t$ given in \cite{KC17} where a dynamic evolving $k_t$-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 $\lfloor \beta t\rfloor$ for a real $\beta\in(0,1)$, then we have a dynamic evolving threshold secret sharing scheme with the share size $O(t^{4\beta})$. For $\beta<0.25$, this scheme has sub-linear share size which was not known before. Our last scheme is an evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme with constant share size. 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 \cite{KC17} can also transform all of our schemes to a robust scheme as our scheme is linear.\footnote{We note that by replacing the building block scheme with an arithmetic secret sharing scheme, the evolving $(\Ga t,\Gb t)$-ramp secret sharing scheme in \cite{BO20} can also be multiplicative. However, their share size is much bigger than ours as each party hold multiple shares. }