Threshold Cryptography | MIT CSAIL Theory of Computation

CIS members involved:

Former Students: Stanislaw Jarecki, Anna Lysyanskaya

Idea: The idea of theshold cryptography is to protect information (or computation) by fault-tolerantly distributing it among a cluster of cooperating computers. First consider the fundamental problem of threshold cryptography, a problem of secure sharing of a secret. A secret sharing scheme allows one to distribute a piece of secret information among several servers in a way that meets the following requirements: (1) no group of corrupt servers (smaller than a given threshold) can figure out what the secret is, even if they cooperate; (2) when it becomes necessary that the secret information be reconstructed, a large enough number of servers (a number larger than the above threshold) can always do it.

A very useful extension of secret sharing is function sharing. Its main idea is that a highly sensitive operation, such as decryption or signing, can be performed by a group of cooperating servers in such a way that no minority of servers is able to perform this operation by themselves, nor would they be able to prevent the other servers from performing the operation when it is required.

Motivation: In many real-life situations, we don't believe that any given person can be trusted, and we may even suspect that a big fraction of all people are dishonest, yet it is reasonable to assume that the majority of people are trustworthy. Similarly, in on-line transactions, we may doubt that a given server can be trusted, but we hope that the majority of servers are working properly. Based on this assumption, we can create trusted entities. A good example of an application whose security could be greatly improved with a threshold solution is a network Certification Authority, a trusted entity that certifies that a given public key corresponds to a given user. If we trust one server to perform this operation, then it is possible that as a result of just one break-in, no certificate can any longer be trusted. Thus it is a good idea to distribute the functionality of the certification authority between many servers, so that an adversary would need to corrupt half of them before he can forge a certificate on some public key.

A certification authority is really a signature service: The public-key certificates it produces are signatures on messages that contain a description of some entity and its public key. Therefore, to implement such certification authority in a fault-tolerant threshold manner described above we need secure threshold signature schemes. There are many other function-sharing applications, including applications for distributed decryption. Threshold decryption schemes enable such operations as key recovery, organization's keys, fair sale of digital content in exchange for digital receipts; secure bidding, and secret election protocols.

Goals: In the threshold setting, we would like to implement, via efficient protocols, the most secure cryptosystems and signature schemes. We would also like to make our protocols secure in the strongest possible model of faults. The following are some of the various considerations we make when modeling computer faults:

The size of the threshold: What fraction of the servers can be corrupted by the adversary without any harm to the service (e.g. signature or decryption) that these servers implement?

Efficiency considerations: How much communication, storage, and computation do these fault-tolerant protocols require?

Model of commmunication: How realistic are the requirements we place on it? Do we require synchronous or partially synchronous communication, authenticated broadcast and secure links between servers?

Type of adversary we tolerate: How does the adversary choose which players to corrupt? Can a server securely erase its local data so that it cannot be retrieved by the adversary once the server is infiltrated?

Below we give a more detailed explanations of our results, and links to the papers themselves, in reverse chronological order:

Results (1999-2001)
Results from previous years (1995-1998)

Results (1999-2001):

[LP01] Anna Lysyanskaya, Chris Peikert. "Adaptive security in the threshold setting: From cryptosystems to signature schemes." ASIACRYPT 2001. (.ps)

Threshold cryptosystems and signature schemes give ways to distribute trust throughout a group and increase the availability of cryptographic systems. A standard approach in designing these protocols is to base them upon existing single-server systems having the desired properties.

Two recent (single-server) signature schemes, one due to Gennaro et al., the other to Cramer and Shoup, have been developed which are provably secure using only standard number-theoretic hardness assumptions. Catalano et al. proposed a statically secure threshold implementation of these schemes. We improve their protocol to make it secure against an adaptive adversary, thus providing a threshold signature scheme with stronger security properties than any previously known.

As a tool, we also develop an adaptively secure, erasure-free threshold version of the Paillier cryptosystem.

[JL99] Stanislaw Jarecki, Anna Lysyanskaya. "Adaptively secure threshold cryptosystems without erasures." Manuscript, 1999.

This paper provides solutions for efficient threshold cryptosystems which are secure against adaptive adversaries even when the players cannot erase their local data. Specifically, it presents erasure-free adaptively-secure protocols for distributed key generation in discrete-log based schemes, for DSS and RSA signature generation, and for ElGamal decryption. Recently, [CGJKR99] introduced efficient adaptively-secure threshold cryptosystems whose security relies on the ability of the uncorrupted players to safely erase most of the secret data they produce during the protocol execution. However, secure erasure of data is hard to implement in practice: It requires specialized hardware and operating systems, and even then it would remain a costly operation.

This work builds directly on the protocols of [CGJKR99] for distributed generation of keys in discrete-log based cryptosystems, and for distributed generation of DSS and RSA signatures. By introducing a few subtle but crucial modifications to these protocols, and using novel techniques in the analysis of their security, thee need to recourse to erasures in these protocols is removed. These modifications actually reduce the complexity of the adaptively-secure RSA signature generation. However, in the key generation and DSS signature generation protocols, an increase in communication and computation complexity over the efficient [CGJKR99] protocols which is sublinear in the security parameter is incurred.

The sublinear increase in complexity is wholly due to the implementation of secure channels we use to make our protocols secure in the adaptive model. In contrast, the best currently known implementation of secure channels for general adaptively-secure erasure-free multiparty computation based on the DDH assumption, due to Beaver, creates an overhead which is linear in the security parameter.

[L99] Anna Lysyanskaya. "Efficient threshold and proactive cryptography secure against the adaptive adversary." Manuscript, 1999.

The contributions of [CGJKR99] are extended in two main directions: (1) for the first time in threshold cryptography, practical distributed cryptographic systems that are secure against the adaptive adversary in the concurrent setting are proposed; and (2) simple and clean methods for achieving security against the adaptive adversary are presented. The new techniques presented in this paper make it possible to extend the contribution of [CG99] and implement the threshold version of the Cramer-Shoup cryptosystem such that it withstands active attacks from the adaptive adversary. This is the most secure known practical threshold cryptosystem, since the underlying Cramer-Shoup cryptosystem is secure against adaptive chosen ciphertext attack. Note that these techniques are of independent interest because they apply to transforming virtually any discrete-logarithm-based cryptosystem into its threshold counterpart secure against the adaptive adversary.

[CGJKR99] Ran Canetti, Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin. "Adaptive Security for Threshold Cryptosystems." Appeared in CRYPTO'99.

(postscript of an extended version)

This paper presents adaptively secure efficient solutions to several central problems in the area of threshold cryptography. The solutions withstand adaptive attackers taht choose parties for corruption at any time during the run of the protocol. In contrast, all previously known efficient protocols for these problems were proven secure only a less realistic static adversaries that choose and fix the subset of corrupted parties before the start of the protocol run.

Specifically, adaptively secure solutions for distributed key generation in discrete-log based cryptosystems are provided, and for the problem of distributed generation of DSS signatures (threshold DSS). It is also shown how to transform existent static solutions for threshold and proactive RSA to withstand the stronger adaptive attackers. To solve these problems we introduce several techniques for the design and analysis of adaptively secure protocols that may find further applications. Our work directly improves on the previous results on threshold generation of keys for DLog-based systems [GJKR99], threshold DSS [GJKR96a] and threshold RSA [GJKR96b], which were all provably secure in only the non-adaptive adversarial model.

[CG99] Ran Canetti, Shafi Goldwasser. "An efficient threshold public-key cryptosystem secure against adaptive chosen ciphertext attack." Appeared in EUROCRYPT'99, pp.90-106

This paper proposes a simple threshold Public-Key Cryptosystem (PKC) which is secure against adaptive chosen ciphertext attack, under the Decisional Diffie-Hellman (DDH) intractability assumption.

Previously, it was shown how to design non-interactive threshold PKC secure under chosen ciphertext attack (CCA), in the random oracle model and under the DDH intractability assumption. The random oracle was used both in the proof of security and to eliminate interaction. General completeness results for multi-party computation enable in principle to convert any single-server PKC secure against adaptive CCA into a threshold one, but the conversions are inefficient and require much interaction among the servers for each ciphertext decrypted.

The recent work of Cramer and Shoup on single server PKC secure against adaptive CCA is the starting point for the new proposal.

[GJKR99] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin. "Secure Distributed Key Generation for Discrete-Log Based Cryptosystems." Appeared in EUROCRYPT'99, pp.295-310.

(postscript of an extended version)

Distributed key generation is a main component of threshold cryptosystems and distributed cryptographic computing in general. Solutions to the distributed generation of private keys for discrete-log based cryptosystems have been known for several years and used in a variety of protocols and in many research papers. However, these solutions fail to provide the full security claimed and required by these works. This paper shows how an active attacker controlling a small number of parties can bias the values of the generated keys, thus violating basic correctness and secrecy requirements of a key generation protocol. In particular, these attacks point to the places where the proofs of security fail.

Based on these findings a distributed key generation protocol presented here is designed and together a rigorous proof of its security is provided. This protocol, which achieves optimal resiliency, can be used as a drop-in replacement for key generation modules as well as other components of threshold or proactive discrete-log based cryptosystems, including [HJJKY97], [GJKR96a], and in [HJKY95].

Results from years 1995-1998:

[HJJKY97] Amir Herzberg, Markus Jakobsson, Stanislaw Jarecki, Hugo Krawczyk, Moti Yung. "Proactive Public Key and Signature Systems"; Appeared in ACM Security'97.  (postscript available)

We propose a proactive approach for the protection of sensitive private key operations, e.g. signatures and decryption, that are at the heart of the security of public key systems and the applications they protect (like secure communications and electronic commerce). This approach combines threshold cryptosystems (where the ability to perform these private key operations requires the cooperation of several parties, as in [GJKR96a] or [GJKR96b]) with the periodic refreshment and integrity protection of local shares (as in Proactive Secret Sharing of [HJKY95]). As a result, the only way that an attacker can get access to these sensitive operations is by breaking simultaneously into several locations during a short period of time, say a day or a week, even though the protected key may live unchanged for long terms (like few years). We present such proactive solutions for a variety of discrete log based cryptosystems including DSS and Schnorr signatures, ElGamal-like signatures and encryption, undeniable signatures, and more. We build on previous work on proactive secret sharing and threshold schemes, and develop a general methodology for the combination of many of these systems into secure proactive public key solutions.

[GJKR96b] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. "Robust and Efficient Sharing of RSA Functions "; Appeared in CRYPTO'96.

(a postscript of journal version available)

We present two efficient protocols which implement robust threshold RSA signature schemes, where the power to sign is shared by N players such that any subset of T+1 or more signers can collaborate to produce a valid RSA signature on any given message, but no subset of T or less corrupted players can forge a signature. Our protocols are robust in the sense that the correct signature is computed even if up to T players behave in arbitrarily malicious way during the signature protocol. This, in particular, includes the cases of players that refuse to participate or that introduce erroneous values into the computation. Our robust protocols achieve optimal resiliency as they can tolerate up to (N-1)/2 faults, and their efficiency is comparable to the efficiency of the underlying threshold RSA signature scheme. Our protocols require RSA moduli which are the product of two safe primes, and that the underlying (centralized) RSA signature scheme is unforgeable. Our techniques also apply to the secure sharing of the RSA decryption function.

We show that adding robustness to the existing threshold RSA schemes reduces to solving the problem of how to verify an RSA signature without a public verification exponent. Our technical contribution focuses on solving this problem. Once a solution to this problem exists it can be applied to any existing threshold RSA signature scheme in order to achieve a robust threshold safe prime RSA signature scheme.

Our solutions to the above problem are based on some interesting extensions that we devised for the information checking protocol of T. Rabin and Ben-Or, and the undeniable signature work initiated by Chaum and van Antwerpen. These extensions have some attractive properties, and hence are of independent interest.

[GJKR96a] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. "Robust Threshold DSS Signature "; Appeared in EUROCRYPT'96.

(a postscript of a journal version available)

We present threshold DSS (Digital Signature Standard) signatures where the power to sign is shared by n players such that for a given parameter t, where t is less than n/2, any subset of 2t+1 signers can collaborate to produce a valid DSS signature on any given message, but no subset of t corrupted players can forge a signature (in particular, cannot learn the signature key). In addition, we present a robust threshold DSS scheme that can also tolerate n/3 players who refuse to participate in the signature protocol. We can also endure n/4 maliciously faulty players that generate incorrect partial signatures at the time of signature computation. This results in a highly secure and resilient DSS signature system applicable to the protection of the secret signature key, the prevention of forgery, and increased system availability.

Assuming that secret communication between the players is available, we prove the security of our protocols solely based on the hardness of forging a regular DSS signature.

[HJKY95] Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung. "Proactive Secret Sharing, or How to Cope with Perpetual Leakage"; Appeared in CRYPTO'95.

(an extended postscript version available)

Secret sharing schemes protect secrets by distributing them over different locations (share holders). In particular, in k out of n threshold schemes, security is assured if throughout the entire life-time of the secret the adversary is restricted to compromise less than k of the n locations. For long-lived and sensitive secrets this protection may be insufficient.

We propose an efficient proactive secret sharing scheme, where shares are periodically renewed ( without changing the secret) in such a way that information gained by the adversary in one time period is useless for attacking the secret after the shares are renewed. Hence, the adversary willing to learn the secret needs to break to all k locations during the same time period (e.g., one day, a week, etc.). Furthermore, in order to guarantee the availability and integrity of the secret, we provide mechanisms to detect maliciously (or accidentally) corrupted shares, as well as mechanisms to secretly recover the correct shares when modification is detected.