A new threshold changeable secret sharing scheme based on the Chinese Remainder Theorem

A general (t, n) secret sharing (SS) scheme with fixed threshold allows a secret to be shared without considering the time dynamic nature of the security environment. In this paper, we propose a threshold changeable secret sharing scheme whose threshold can be changed in an integer interval [t, t′] without updating the shares. In this scheme, a different threshold can be activated at any time through the public broadcast channel. At the heart of the proposed scheme is a novel matrix of primes. The validity of the share generation and secret reconstruction is provided by the Chinese Remainder Theorem (CRT). We prove the existence of the proposed matrix and present a method to efficiently construct it, which makes use of a proposed sequence of nested closed intervals generated by large co-prime numbers. We further use the structure to propose a scheme with computational security, without maintaining online dealer. Compared with previous methods, the proposed scheme has short share size and low complexity for recovery. For any changeable threshold in [t, t′], the increase in share size is at most 1t−1 of that from previous methods. Computational complexity for secret recovery is O(t), compared with O(tlog2t) of the best previous methods.