risk management using threshold RSA cryptosystems

by Yair Frankel
<yfrankel@cs.columbia.edu>

Yair Frankel is a vice president at CertCo LLC. His main interest is cryptography and computer security with a special interest in distributed trust mechanisms.

and Moti Yung
<moti@certco.com, moti@cs.columbia.edu>

Dr. Moti Yung is a vice president and a cryptographer of CertCo LLC, working in cryptography, security, and electronic commerce. His research interests include information technology, networking, fault tolerance, algorithms, and theory of computing.

A certification authority (CA) in a public-key infrastructure provides the trust mechanism through digital signature generation to create users' public-key certificates. Because the whole public-key infrastructure is based on the security of the CA, security mechanisms must be used to manage the risk of the CA.

One method of managing risk is by distributing trust to multiple parties so that no single entity can compromise the system. In fact, the distributed root certification key for MasterCard/VISA's Secure Electronic Transaction (SET) root uses threshold cryptography mechanisms. Such distributed trust mechanisms can provide enhanced security protection against internal collusions as well as external attacks by eliminating the centralized control; forcing the adversary to take more risks (and to pay more) because it must penetrate several systems rather than just one (and in proactive systems it is also limited to doing it in a small period of time).

The SET CA is not controlled by one business entity, but rather by multiple corporate entities. The threshold RSA cryptosystem mechanisms can provide for a cryptographic tool that establishes a form of risk sharing among multiple entities, each with its own security policy. That is, threshold cryptosystems can be set up so that nonrepudiation is shared under a single signature. The extent to which the signature generation is shared is defined by the access structure the corporate entities have agreed upon.

Recently, there has been a thrust to construct more efficient protocols for specific problems, particularly those involving the distributed application of cryptographic functions (surveyed in an invited paper "A New Directions in Cryptography: Twenty Something Years After," by S. Goldwasser in Symposium on Foundations of Computer Science (FOCS) '97.). Here we focus on what has recently been achieved with efficient threshold RSA cryptosystems because RSA is the most commonly used digital signature algorithm today. Though we primarily discuss the RSA algorithm, similar results are possible with other cryptographic algorithms. A more complete survey by Frankel and Yung "Distributed Public Key Cryptosystems," will be published in the Proceedings of Public Key Cryptography (PKC) '98.

Sharing a Secret Key

Threshold schemes are the traditional cryptographic example of how to securely and reliably distribute a key. With a (t,v)-threshold scheme, a secret value is shared via v shadows such that less than a quorum (i.e., at least t) of shadows does not reveal the secret value. During a secret reconstruction phase, any quorum of shadows may be used to efficiently reconstruct the secret value; however, anyone possessing less than a quorum of shadows learns nothing about the secret key. Threshold structures (i.e., any set of t out of v) are not the only possible access structures that have been investigated.

Distributed Function Application

Threshold schemes are defined as a onetime application. Once the secret is regenerated it is known by some entity. Threshold schemes can be used as a building block for distributing cryptographic functions such as a digital signature.

Our focus is on systems in which a secret function (e.g., an RSA signature function keyed with the CA's private key) is shared among a group of servers. In essence, a (t,v)-secure distributed function application protocol shares a keyed cryptographic function f(k,.), where f is a public algorithm and k is a secret key, such that only t or more of v servers can apply the function f(k,.) on an input m to obtain f(k,m). For security, a subset of smaller subsets cannot evaluate the function on input m.

An important property that we desire in distributed trust mechanisms is transparency. A secure function application protocol is transparent if its input specification providing the point of evaluation and output specification providing the function's output is independent of the protocol's access structure. Transparency implies that the external network providing the input/output to the protocol can use the distributed trust mechanism without knowing its inner workings or even which computers provide this service, thus providing a transparent service.

In the certification authority example discussed in the introduction, the function f is the signature algorithm, such as RSA, and the secret k is the private key of the certification authority. The transparency property allows the verifiers of certificates to be unaware whether the certificate was generated using only one certification agent or was created with multiple servers. This allows for any generic digital signature verification software to work independent of how many servers were used to generate the digital signature (certificate).

Based on secret sharing schemes and tamper-proof devices, one can develop a secure function evaluation system. A tamper-proof device is a computational device whose state and memory contents are private even to its owner. Hence, the owner gets only input/output access to the device. To build a secure function evaluation system, one encloses the algorithm in the tamper-proof device. To perform function application, a quorum of shareholders transmits their share to the device, and the device computes the secret key k. The device can perform function application on function f(k,.) for any input m. Only the tamper-proof device learns the key in this process.

The main concern of this tamper-proof-based system is that it relies on a single trusted entity, the tamper-proof device. Because tamper-proof devices do not really exist (and are generally called tamper-resistant), this approach may be unacceptable in some cases, depending on whether one believes these protection mechanisms are sufficient to manage the risk based on the liability that may be incurred due to compromise of the hardware device.

Non-Hardware-Based Solutions

General compiler protocols provide for the evaluation of a circuit (similarly, function) in a distributed manner such that each party in the computation learns nothing more than the output and its own secret components of the function's input. These protocols securely compute any public function on secure inputs. The primary difficulty with general compiler protocols is that such systems are ordinarily inefficient with respect to communication complexity due to their general nature of being applicable to any circuit or arithmetic operations. However, they constitute a "plausibility result" for many tasks. (For a survey of results until 1993 see the doctoral thesis "Complexity and Security of Distributed Protocols" at Columbia University, available at <http://www.cs.columbia.edu/home/phd_prog/alumni.html>).

Threshold cryptography, also called function sharing, takes the less general approach; however, efficiency has been greatly reduced. Whereas the communication complexity of the secure function evaluation depends linearly on the actual size of the circuit computing the cryptographic functions, the communication complexity of function sharing is independent of the circuit size (and is typically a polynomial in the input/output size and the number of participants). This difference is crucial to practitioners because the communication latency cannot compete with increases in processor speeds.

The first threshold RSA cryptosystems were based on (v,v)-secret sharing in "Digital Multisignatures" (the IMA Conference on Cryptography and Coding by C. Boyd) and in "A Practical Protocol for Large Group Oriented Networks" (Eurocrypt '89 by Y. Frankel). Though these schemes can be converted into (t,v)-threshold RSA schemes, they become inefficient for some parameters (e.g., grow exponentially for v/2 out of v schemes). For small v, however, these systems are very efficient and provide a practical solution to distribute an RSA certification.

Proactive Security

The notion of "proactive security" (against a mobile adversary) provides enhanced protection of memories of long-lived cryptographic keys that may be distributed (i.e., protected by "space diffusion"). Proactive security adds protection by "time diffusion" as well. Namely, given a distributed function via threshold cryptography (function sharing) as described, it adds a periodic refreshing of the contents of the distributed servers' memories. This refreshing is a t-wise rerandomization of the local servers' values in a way that preserves the global key but makes previous contents of any set of less than t out of the v servers "useless."

Proactive security renders useless the knowledge of the mobile adversary (e.g., hackers, viruses, bad administrators, etc.) obtained in the past from compromising less than the allowed t servers and gives the system a self-securing nature. Proactive security is an important risk management tool, especially in environments such as a CA, where a long-term public key must be maintained. With proactive security, the shares are updated, so a mobile adversary has to act quickly before the next update, although the public key is not modified during each rerandomization process.

Proactive RSA was first solved in "Proactive RSA" in Crypto '97 by Y. Frankel, P. Gemmel, P. MacKenzie, and M. Yung. The same authors recently developed the first optimal resilience (up to a majority of arbitrarily misbehaving servers can "control" the computation) proactive RSA threshold cryptosystem, "Optimal Resilience Proactive Public-Key Cryptosystems" in the Symposium on Foundations of Computer Science (FOCS) '97. That is, optimal resilience achieves v >= 2(t - 1) + 1.

Secure Key Generation

Another important step regarding distributed cryptographic functions is the (efficiently) distributed generation of the function (the key shares). For cryptographic functions based on modular exponentiation over a field (whose inverse is the discrete logarithm, which is assumed to be a one-way function), a protocol for the distributed generating keys was known for quite a while. However, for the RSA function, which requires the generation of a product of two primes and an inverse of a public exponent, this step was an open problem for many years. A major step forward was recently achieved in D. Boneh and M. Franklin, "Efficient Generation of Shared RSA Keys" in Crypto '97 by Boneh and Franklin (see <http://theory.stanford.edu/~dabo/publications.html>). They showed how a set of participants can generate an RSA function efficiently.

Boneh et al. developed many important new protocol techniques and showed that their protocol was secure in the limited model of "trusted but curious" parties. They left open the issue of robustness, i.e., generation in the presence of misbehaving (malicious) parties (whereas the Boneh-Franklin protocol may be prevented from ever generating a shared RSA key by such behavior). Recently, robust efficient distributed RSA key generation was developed by Y. Frankel, P. MacKenzie, and M. Yung in "Robust Efficient Distributed RSA-Key Generation" in the upcoming Annual Symposium on Theory of Computing (STOC) '98.

Explicit Trust Distribution

Transparency implies that the external environment providing the input/output to the protocol is transparent of the trust mechanism. This, however, is not always necessary (and may sometimes even be undesirable). But explicit trust mechanisms are designed with operations that are meant to be traced or followed explicitly (and not to remain hidden). The idea is that the trail of participants is noticeable in the result of the protocol, a property that may be desirable. In some cases, for instance, instead of using threshold RSA techniques, using one signature by each CA entity may be the simplest and most appropriate technique.