2024/02/02 by Cheng, Qi, Cao, Hongru, Lin, Sian-Jheng +1 · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2402.01144
The threshold secret sharing scheme allows the dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional (k, n)-threshold secret sharing scheme requests that the number of participants n is known in advance. In contrast, the evolving secret sharing scheme allows that n can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Using the prefix codes and the properties of the polynomial ring, we propose a brand-new construction of evolving k-threshold secret sharing scheme for an ℓ-bit secret over a polynomial ring, with correctness and perfect security. The proposed schemes establish the connection between prefix codes and the evolving schemes for k≥2, and are also first evolving k-threshold secret sharing schemes by generalizing Shamir's scheme onto a polynomial ring. Specifically, the proposal also provides an unified mathematical decryption for prior evolving 2-threshold secret sharing schemes. Besides, the analysis of the proposed schemes show that the size of the t-th share is (k-1)(ℓt-1)+ℓ bits, where ℓt denotes the length of a binary prefix code of encoding integer t. In particular, when δ code is chosen as the prefix code, the share size achieves (k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg (\lfloor\lg t\rfloor+1) \rfloor+ℓ, which improves the prior best result (k-1)\lg t+6k4ℓ\lg\lg t⋅\lg\lg \lg t+ 7k4ℓ\lg k, where \lg denotes the binary logarithm. When k=2, the proposed scheme also achieves the minimal share size for single-bit secret, which is the same as the best known scheme.