Abstract: Proposed in this paper is an efficient (k, n) threshold digital signature scheme based on the elliptic curve. In the scheme, k out of n signers cooperate to iss ue a signature, while Nyberg-Ruepple digital signature scheme and Pedersen's ver ifiable secret sharing (VSS) are employed. This new scheme enhances the security of the existing threshold digital signature scheme by redistributing the privat e key d of the signature periodically into the different access structures. This design is not only more difficult for adversary to attack the threshold digital signature scheme, but also flexible for adding or deleting one or more signatur e participants. Assuming that secret communication between the signers is availa ble, the security performances of the scheme are discussed. The advantage of the new scheme has capability of intrusion tolerance besides the property of verifi able partial signature which verifiable threshold signature scheme should have.