Paper 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.

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

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Asiacrypt 2002
Keywords
threshold cryptography
Contact author(s)
jkatz @ cs umd edu
History
2003-06-23: last of 3 revisions
2001-11-07: received
See all versions
Short URL
https://ia.cr/2001/093
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/093,
      author = {Jonathan Katz and Moti Yung},
      title = {Threshold Cryptosystems Based on Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2001/093},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/093}},
      url = {https://eprint.iacr.org/2001/093}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.