[Resource Topic] 2001/093: Threshold Cryptosystems Based on Factoring

Resource No category
#1

Welcome to the resource topic for 2001/093

Title:
Threshold Cryptosystems Based on Factoring

Authors: Jonathan Katz, 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.

ePrint: https://eprint.iacr.org/2001/093

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .