@article {15091,
	title = {Threshold cryptosystems based on factoring},
	journal = {Advances in Cryptology{\textemdash}ASIACRYPT 2002},
	year = {2002},
	month = {2002///},
	pages = {139 - 147},
	abstract = {We consider threshold cryptosystems over a composite modulus N where the factors of N are shared among the participants as the secret key. This is a new paradigm for threshold cryptosystems based on a composite modulus, differing from the typical treatment of RSA-based systems where a {\textquotedblleft}decryption exponent{\textquotedblright} is shared among the participants. Our approach yields solutions to some open problems in threshold cryptography; in particular, we obtain the following:1  	Threshold Homomorphic Encryption. A number of applications (e.g., electronic voting or efficient multi-party computation) require threshold homomorphic encryption schemes. We present a protocol for threshold decryption of the homomorphic Goldwasser-Micali encryption scheme [34], answering an open question of [21].
2  	Threshold Cryptosystems as Secure as Factoring. We describe a threshold version of a variant of the signature standards ISO 9796-2 and PKCS$\#$1 v1.5 (cf. [39, Section 11.3.4]), thus giving the first threshold signature scheme whose security (in the random oracle model) is equivalent to the hardness of factoring [12]. Our techniques may be adapted to distribute the Rabin encryption scheme [44] whose semantic security may be reduced to the hardness of factoring.
3  	Efficient Threshold Schemes without a Trusted Dealer. Because our schemes only require sharing of N - which furthermore need not be a product of strong primes - our schemes are very efficient (compared to previous schemes) when a trusted dealer is not assumed and key generation is done in a distributed manner.
Extensions to achieve robustness and proactivation are also possible with our schemes.
Work done while at Columbia University and Telcordia Technologies
},
	doi = {10.1007/3-540-36178-2_12},
	author = {Katz, Jonathan and Yung,M.}
}
