V S enables the recipient of a digital signature, who is not necessarily the original signer, to share that signature among n proxies so that a subset of them can later reconstruct it. Efficient protocols were also given for RSA, Rabin, ElGamal, Schnorr, and DSS signatures. However, their RSA and Rabin V S protocols were subsequently broken and their DSS V S lacks a formal proof of security. We present new protocols for RSA, Rabin, and DSS V S. Our protocols are efficient and provably secure and can tolerate the malicious behavior of up to half of the proxies. The RSA V S scheme is based on a completely novel approach. The recipient of the signature will not share it using conventional secret sharing schemes, but instead will simply encrypt it using a threshold cryptosystem, i.e., a public key whose matching secret key is kept shared at the proxies. She will then also provide the proxies with a proof that the ciphertext indeed contains a signature. The crux of the problem was to design a threshold cryptosystem that would make such a proof efficient. We present several variants of our basic scheme, one of which requires no interaction between the recipient of the signature and the proxies to establish such a proof and one in which the reconstruction of the signature by the proxies is completely non-interactive. The RSA V S scheme can be easily adapted to Rabin's signatures. The DSS V S scheme is a modified version of the ElGamal V S scheme mentioned above which allows for a proof of security. The main application of V S is