The secret sharing is the basic conecpt of the threshold cryptosystem that divides the single private key in the public key cryptosystem to protect the private key. It is applied to many cryptograhpic applications like the electronic voting , group signature and broadcast encryption. And for its subfield, the (k,n) threshold scheme is defined that at least k of the n shares need to reconstruct the secret information.
The proactive secret sharing is the solution of the existing of the mobile adversary that attacks the entire system in each period of time. The essance of the proactive secret sharing is that the participants perform the share renewal operation in each period before the mobile adversary has the shares more than the threshold values. So if the adversary doesn't have the shares more than threshold value in one share renewal period, They must recollect the shares. The shares that collects in the old period makes useless by the share renewal operation.
In 1995, Jarecki proposed the share renewal scheme for the proactive secret sharing in (k,n) threshold scheme. But his method needs $O(n^2)$ modular exponentiation per one paticipant. It is very high computational cost and does not fit the scalable cryptosystem that has 100 or more participants.
In the thesis, we propose the efficient share renewal scheme that need $O(n)$ modular exponentiation per each participant. In old scheme, the participants in the protocol have the k private value each. But our scheme needs only constant private value per each participant. So they need only $O(n)$ modular exponentiation to verify the private values of all the other participants. Our scheme is more efficient performance if the k value is more than 7. In general, the k value is in $\frac{1}{3}~\frac{1}{2}n$. So if the participants are more than 14~21, our scheme is faster than the old scheme.
For the proving the security of our scheme, we use the simlator using the random oracle model. By using the simulator, we proves that our scheme is secure if the less than $k~(\frac{1}{2}n-1)$ adversaries exist and they are static adversaries.
