Threshold cryptosystems based on factoring

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 “decryption exponent” 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