Proactive multi-secret sharing scheme based on Lagrange interpolation and Chinese remainder theorem

In a proactive secret sharing scheme, a set of secrets are distributed among a set of participants in such a way that: 1) the participants’ shares could be renewed in certain time periods without the aid of the dealer, and 2) while some specific subsets of the participants, called authorized subsets, are able to reconstruct the secrets, other subsets could not obtain any information about the secrets. To the best of our knowledge, there exists only one proactive multi-secret sharing scheme in the literature. This scheme can be considered as the combination of a well-known proactive (single) secret sharing scheme and the one-time-pad encryption system. This scheme is only weakly secure meaning that the disclosure or reconstruction of one of the secrets in this scheme would be lead to the disclosure of all the secrets. In addition to being weakly secure, this scheme reconstructs all the secrets at once and does not provide gradual reconstruction of the secrets. To solve these problems, we use Lagrange interpolation and the Chinese remainder theorem in this paper and propose a new proactive multi-secret sharing scheme. The proposed scheme is a strongly secure proactive multi-secret sharing scheme. It allows gradual reconstruction of the secrets in a predetermined order and provides verifiability using the intractability of discrete logarithm problem.