Paper 2026/2619

Smaller Share Size for Evolving Secret Sharing: General Thresholds and Threshold Three

Abstract

Evolving secret sharing allows participants to join indefinitely without modifying previously distributed shares. We study the share size of perfectly secure evolving threshold secret sharing schemes and obtain two improvements. For general thresholds, we introduce a polynomial sharing method that shares two secrets with adjacent reconstruction thresholds using one polynomial. Combining this method with the evolving scheme of Cheng et al.\ (ASIACRYPT 2025), we obtain an evolving $k$-threshold scheme whose $t$-th share has size \[ \left\lfloor \frac{k}{2} \right\rfloor \log_2 t + O_k\!\left(\ell+\log_2\log_2 t\right) \] bits for an $\ell$-bit secret. This reduces the leading coefficient of their general construction from $k-1$ to $\lfloor k/2\rfloor$. For threshold three, we give a separate construction that reduces the lower-order terms of the scheme of Cheng et al. We mask the short shares in all generations with the same random $\ell$-bit value $R$, which is shared through an evolving $2$-threshold scheme, we obtain \[ \log_2 t+(2+o(1))\log_2\log_2 t \] bits per share for fixed $\ell$. Both constructions satisfy correctness and perfect information-theoretic security.