New Efficient and Secure Protocols for Verifiable Signature Sharing and Other Applications

摘要

Verifiable signature sharing (VΣS) was introduced by Franklin and Reiter in “Eurocrypt '95” (Lecture Notes in Computer Science, Vol. 921, pp. 50–63, Springer-Verlag, Berlin, 1995). 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 the incorporation of digital cash into multiparty protocols, e.g., cash escrow and secure distributed auctions. Our protocols thus provide simple, efficient, and secure solutions for those applications. Furthermore we believe that some of our techniques are of independent interest. Some of the by-products of our main result are a new threshold cryptosystem, a new undeniable signature scheme, and a way to create binding RSA cryptosystems.