Abstract: Based on ElGamal cryptosystem, a new verifiable secret sharing scheme was proposed. In this scheme, each participant's secret shadow is selected by the participant himself and even the secret dealer does not know anything about his secret shadow. All these shadows arc as short as the secret to be shared. In the recovery phase, any participant computes only one time in order to detect if cheats exist and the probability of successfully cheating can be ignored. The secret dealer can point out the identity of cheats if they exist. For this scheme, the secret information is fully used and the computation complexity of verifying can be reduced largely. The shadows do not need to be changed when the shared secret is renewed. Moreover, each participant can share many secrets with other participants by holding only one shadow. The security of this scheme is the same as that of the ElGamal cryptosystem and Shamir's (t,n) threshold secret sharing scheme.

Key words: ElGamal scheme, Verifiable secret sharing, Shamir's threshold scheme