Cryptology ePrint Archive: Report 2001/093

Threshold Cryptosystems Based on Factoring

Jonathan Katz and Moti Yung

Abstract: We consider threshold cryptosystems over a composite modulus $N$ where the \emph{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. \emph{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 \cite{GM84}, answering an open question of \cite{FPS00}.

2. \emph{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.\ \cite[Section 11.3.4]{MvOV}), thus giving the first threshold signature scheme whose security (in the random oracle model) is equivalent to the hardness of factoring \cite{C02}. Our techniques may be adapted to distribute the Rabin encryption scheme \cite{R79} whose semantic security may be reduced to the hardness of factoring.

3. \emph{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.

Category / Keywords: threshold cryptography

Publication Info: Asiacrypt 2002

Date: received 7 Nov 2001, last revised 23 Jun 2003

Contact author: jkatz at cs umd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Corrected an error (pointed out by J.B. Nielsen) in the description of the methods for achieving robustness.

Version: 20030623:182447 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]