We consider threshold cryptosystems over a composite
modulus where the \emph{factors} of 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 --- 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.
@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},
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.