CryptoDB
Threshold Cryptosystems Based on Factoring
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2001-11505,
title={Threshold Cryptosystems Based on Factoring},
booktitle={IACR Eprint archive},
keywords={threshold cryptography},
url={http://eprint.iacr.org/2001/093},
note={Asiacrypt 2002 jkatz@cs.umd.edu 12226 received 7 Nov 2001, last revised 23 Jun 2003},
author={Jonathan Katz and Moti Yung},
year=2001
}