Optimal-resilience proactive public-key cryptosystems

Optimal-Resilience Proactive Public-Key Cryptosystems Yair Frankel

Peter Gemmelly

Abstract We introduce new ecient techniques for sharing cryptographic functions in a distributed dynamic fashion. These techniques dynamically and securely transform a distributed function (or secret sharing) representation between t-out-of-l (polynomial sharing) and t-out-of-t (additive sharing). We call the techniques poly-to-sum and sum-to-poly, respectively. Employing these techniques, we solve a number of open problems in the area of cryptographic function sharing. We design a threshold function sharing scheme with proactive security for general functions with a \homomorphic property" (a class which includes all RSA variants and Discrete Logarithm variants). The sharing has \optimal resilience" (server redundancy) and enables computation of the function by the servers assuring high availability, security and eciency. Proactive security enables function sharing among servers while tolerating an adversary which is mobile and which dynamically corrupts and abandons servers (and perhaps visits all of them over the lifetime of the system, as long as the number of corruptions (faults) is bounded within a time period). Optimal resilience assures that the adversary can corrupt any minority of servers at any time-period. On the way, we solve other open problems: (1) A \share-size ecient robust RSA function sharing" protocol is presented (all previous secure solution had a non-constant blow-up of the permanent share held by servers); (2) A new \robust threshold RSA" scheme for any RSA (not necessarily strong-prime based); (3) We also give a particularly ecient \proactive RSA" as a modular extension of the \share ecient robust system". The techniques also allow dynamic updates to the set of servers employed and to the threshold size.  CertCo LLC, New York, NY; [email protected] y Computer Sci., Univ. of New Mexico, Albuquerque, NM;

[email protected]; (previously with Sandia National Labs). z Boise State University, Boise, ID; [email protected] x CertCo LLC, New York NY; [email protected], [email protected].

Philip D. MacKenziez

Moti Yungx

1 Introduction Proactive robust threshold public-key schemes (introduced in [HJJKY]) are presented for general \homomorphic-type" public-key systems, together with optimized systems for the RSA function. The systems are optimal-resilience, namely the (arbitrary) adversary can corrupt any minority of servers at any time-period; this threshold is a (trivial) upper bound on resilience, even against a weaker stationary adversary. Our techniques give general optimalresilience public-key systems which are \robust threshold" schemes (assuming a stationary adversary), and extensions which give \proactive" systems. Proactive security (introduced in [OY]) employs dynamic memory refreshing activated by the servers to withstand \mobile adversary."

Threshold Cryptography: Threshold cryptography, in particular public-key function sharing, has the spirit of secret sharing

[Bl, Sh] (where a shared secret is recoverable only from a threshold of shareholders). It provides for increased availability of the function service (signature, decryption, etc.) by distributing fk (
) to a set of l servers such that for any valid argument m, any set of at least a given threshold of the servers can compute fk (m). For security, on the other hand, an adversary who controls less than a given threshold t of servers and can hear all of the public messages, obtains no computational advantage in computing fk (m0 ) for a target message m0 as compared to an adversary attacking the centralized function fk (
) with the same capabilities. Thus the function is protected by \space diusion" since an attacker is forced to break the memory of more than a threshold of the function share-holders. (For RSA sharing see [B88, F89, DF91, DDFY]).

Proactive Security:

\Proactive security" provides enhanced protection against a mobile adversary to long-lived cryptographic keys that are already distributed (i.e. protected by \space diusion."). In fact, it adds protection by \time diusion" as well. Namely, given a shared function as described above, it adds a periodic refreshing of the contents of the distributed servers' memories.

This proactive refreshing protocol causes a \t-wise re-randomization" of the local servers' values which preserves the global key but makes previous contents of any set of less than t out of the l servers \useless". Therefore, the knowledge of the mobile adversary (representing: hackers, viruses, bad administrators, etc.) obtained in the past from compromising at most the allowed t-1 number of servers is rendered useless for the future (i.e., this gives the system a selfsecuring nature). The proactive systems for cryptographic functions inherit the availability property of threshold schemes. Proactive systems also use robustness techniques to enhance availability of threshold cryptosystems by tolerating (detecting or correcting) malicious servers who are actively disrupting function evaluation or attacking the availability of the system. It also allows recoveries of the servers' memories which were previously corrupted by the adversary or by non-malicious faults. This gives the system a self-healing nature. As a result, the system can tolerate a \mobile adversary" which is allowed to potentially move among servers over time with the limitation that it can only control up to t ? 1 servers at a time unit. In particular, the adversary may even eventually visit the entire system under the above restriction. Still, the system self-heals from erasures and corruptions of memories by the adversary, and self-secures against the adversary's actions. This is a strictly stronger adversary than a stationary one which corrupts servers in a monotone fashion. Works on proactive security include [OY, CH, HJKY, AGY, HJJKY, FGMY] and a preliminary work, which rst employed shares of shares of secrets to allow servers in a protocol to drop and re-join dynamically [GHY87].

Applications of Proactive Security:

The added advantage of proactivization in practical systems is that in a long-lived threshold system (like RSA for public-key infrastructure) an adversary has a long time (5 years) to break into any t out of the l servers, while in the proactive systems the adversary has only a short period of time (say, a week) to break into any t servers. This protection is seems important in \long-lived" systems which are expected to span the secure network and e-commerce infrastructure. Another application of the \proactive model" is a exible key management of share-holders in a function sharing scheme. It enables, in the refreshing period, to change the set of shareholders (by giving the recovered new share to the new server rather than the old one). Here we extend this capability, enabling dynamic changes

of the threshold value as well.

Eciency:

Function sharing is relevant to practice, thus we concentrate on relatively ecient constructions, where servers evaluating and transmitting cryptographic functions' values. This is in contrast with the inecient communication involved in general compilers known as \secure circuit evaluation" (where the communication is proportional to the size of circuits computing the cryptographic functions when instantiate for our tasks). This distinction in communication eciency was noted in [FY93], and then in [DDFY] in the context of function computation. This seems to give a rst order intuitive separation between two classes of important protocols: (1) general cryptographic compilers (or instantiation of compilers with functions embedded in them) which are typically impractical; and (2) more speci c function protocols which are typically more appealing to practitioners since the communication is independent of the \size" of cryptographic functions' circuits.

On proactive function sharing:

The notion of \proactive public-key" was rst suggested and implemented by [HJJKY]. This implementation was limited to \discrete logarithm" with exponentiation in a prime eld (i.e. given the elements modulo a prime p we use a generator of GF (q) where q divides p ? 1 so that ElGamal decryption or DSS signing can be done [DF89, HJJKY, GJKR1]). This proactivization problem is made possible since key rerandomization involves distributed computation over keys, and the keys in this case are from a domain whose algebraic structure is public (a group of a known order). In contrast, when we deal with functions like the RSA, the problem seems harder since it is de ned over a \secret domain" (namely, a group of order that cannot be known publicly or to the servers). Indeed, maintaining shares of keys and updating their values poses a dierent problem which had been open for a while. More recently, proactivization of RSA was given in [FGMY], however, this rst implementation and its techniques do not lead to \optimal resilience," and for high resilience in a large system it pays a polynomial performance penalty which is somewhat high (while being quite ecient in small scale cases). This problem was left open.

Our Results:

We answer the open question and further generalize it. We present new techniques and protocols and show: 1. An \Optimal resilience Proactive RSA" exists.

(a) We develop the result in stages. First we show how adding a poly-to-sum step to the a threshold RSA cryptosystem (e.g., a general variant of the heuristic scheme in DesmedtFrankel system [DF91]) provides for a \provably secure" threshold scheme. (b) We show how to make our function sharing protocol robust. (c) Then we show that \size ecient secure RSA function sharing" exists where the size of permanent shares and keys is of the same order as the secret's size. Previous solutions (such as [DDFY]) do not have this property. (d) The robust secret sharing is then augmented by new procedures for \share renewal" and \share recovery" which underly the proactive RSA protocol. 2. Our result is extended to apply to many cryptographic functions with a certain homomorphic property. (a) We give properties necessary for a function to be proactivized using our technique, namely 1) share translation, 2) share eciency, and 3) share simulatability of [DDFY] In addition, we require an additional property 4) ring simulatability. (b) Based on the general scheme we can instantiate various cryptosystems, such as a proactive discrete-log system (modulo a composite as well as other algebraic structures). The general scheme is based on algebraic extensions of the key space and, in particular, it enables the rst proactive RSA with a noninteractive function computation phase. 3. The underlying techniques we design are basic \share of shares" methods (poly-to-sum and sumto-poly) which change the representation of a function. Besides allowing us proactivization and allowing us to securely change a threshold sharing scheme by changing the threshold parameter (from t-out-of-l to t-out-of-t and vice versa), they allow us to change t and l dynamically as a system management tool. In fact, we believe that these representation changing techniques are of an independent interest.

2 Background and De nitions

The RSA algorithm:

The RSA key generator G produces two large random

primes p1 and p2 , and computes n = p1
p2 and the Euler toitent function (n) = (p1 ? 1)(p2 ? 1). To compute the secret key, the generator chooses a random d such that gcd(d; (n)) = 1. The public key is n and e where ed  1 mod (n). The one-way (hard) direction of RSA (used in decryption or signature of a message m) is Sm  md mod n, whereas the public (easy) direction (used in encryptions and veri cation of signature) is (Sm )e mod n which gives m.

De nition 1 The RSA security assumption (with respect to a history): Let h be the security parameter. Let key generator GE de ne a family of RSA functions (i.e., (e; d; n) G(1h ) be an RSA instance with security parameter h). For any polynomial poly(
), for h large enough, For any probabilistic polynomial-time adversary A, given a history H containing polynomial-size list L of \authorized messages" and their signatures/decryption:

 Pr[ue  m0 mod n : (e; d; n) 1G(1h ); m0 2CH f0; 1gh; u A(1h ; m0 ; H )] < poly(h) : where 2CH represents the choice of a challenge. The RSA function is a building block for many secure systems where the adversary is allowed to initially access the system and get results based on various restrictions on the input (i.e., chosen plaintext encryption, random plaintext to be signed, etc.). Secure systems typically allow access to random instances (i.e. allowing sampling RSA as a one-way function), thus we assume here that allowed inputs are random.

The Distributed Model:

We use the public-key model of [HJJKY]. We assume our group of l servers securely shares a private key k. The servers are connected to a common broadcast medium C , called the communication channel, with the property that messages sent on C instantly reach every party connected to it. We assume that each server has a local source of randomness and that the system is synchronized (and w.l.o.g. that servers act synchronously). A proactive implementation of the communication model is discussed in [HJKY]. The time is divided into time periods which are determined by the common global clock (e.g., a day, a week, etc.). Each time period consists of a short update phase, during which the servers engage in an interactive update protocol, at the end of which they hold new shares (in fact, a new sharing) of the secret k. After the update, there is a function computation phase, in which the servers perform the intended secret-key operation using their current sharing of k on numerous inputs.

The adversary is computationally bounded and it can corrupt servers at any moment during a time period by viewing the memories of corrupted servers and/or modifying their behavior. The adversary base its corruption decisions on past available message signatures pairs. If a server is corrupted during an update phase, we consider the server as corrupted during both periods adjacent to that update phase. We assume that the adversary corrupts no more than t ? 1 out of l servers in each time period, where l  2(t ? 1) + 1 (this (t-1)-restricted adversary guarantees the existence of a majority of t honest servers at each period). Our model does not dierentiate malicious faults from \normal" server failures (e.g., crashes). We also assume that the adversary is connected to the broadcast channel C , which means he can hear all the messages and inject his own. He cannot, however, modify messages sent to C by a server that he does not control, nor can he prevent a non-corrupted server from receiving a message sent on C . We assume that the adversary intruding on a shareholder is \removable" (e.g., through a reboot procedure) when it is detected. The reboot operation is performed immediately when attacks or deviations from the protocol are detected, and it is shorter than a duration of a time period. We also consider special weaker cases of this malicious (t1)-restricted mobile adversary (static vs. mobile, and passive vs. malicious).

Distributed RSA:

An optimal-robustness proactive RSA system (informally) has the following protocols: (1) an initialization protocol where shares are distributed (e.g., centrally or distributively [BF97]); (2) RSA function (signature) application protocol, where the servers act on a common authorized input and then the combining function generates the nal RSA result eciently; (3) an update phase operation which contains a share renewal protocol and a share loss detection and recovery protocol. We require correctness which means that at any point that a function is needed to be evaluated there are enough honest servers, so that the combination of their shares gives the correct RSA result. We also require robustness so that the combining eort even when up to t parties are adversarial is polynomial-time. We note that a system that has only the initial setup of share dealing and the RSA function application components as above is called \Robust Threshold RSA" (or Robust function-sharing of RSA). A system as above is called secure if (informally) the adversary viewing the system operating on \authorized messages" cannot forge (or decrypt) a new ran-

dom message (which is a successful attack on the RSA function). Formal de nitions of correct and secure systems will be given in the nal paper. We note that to argue about security, we employ the notion of computationally indistinguishable distributions [GM, Y82] which has had an important role in de ning security in many cryptosystems, in particular in the context of encryption and zero-knowledge [GM, GMR1, GMW].

3 A Secure Robust Threshold RSA

We now develop a secure robust threshold RSA. The framework of the protocol is a heuristic threshold RSA scheme which is presented in Section 3.1. Since we cannot show security of the heuristic scheme, we develop a randomization protocol in Section 3.2. The protocol converts the polynomial sharing of the heuristic scheme to a t out of t sum sharing which will be used in the signing. Since it adds randomization which makes the signing shares \less independent" on the long term polynomial shares, it actually converts the heuristic scheme into a provable scheme as will be discussed in Section 3.3. A robustness enhancement is presented in Section 3.4. The diculty turns out to be how to enable robustness by providing checking information which is publicly veri able, and at the same time how not to reduce security. In fact robustness is needed for assuring both correct randomization and for the signing. Previously public veri ability techniques were similar to the partial signing process itself. But, it is not known how to simulate partial signing securely for the heuristic scheme, so new techniques are developed which allow for simulatability. Throughout the rest of the paper let L = l!.

3.1 A heuristic threshold RSA scheme

We now describe the heuristic threshold RSA scheme. Its basic idea is to use the Shamir threshold scheme where inverse computations are easy. RSA is generated by the dealer with a public key (e; n) and a private key d. Let H = gcd(e; L2) and using the extended Euclidean algorithm compute P; s0 2 such 1 = eP + LH s0 . Note that d  P + L2 k0 mod (n) where k0  ds0 H ?1 mod (n). Because e?1 exists, thus H must be invertible, and the dealer can compute k0 from d. The dealer chooses a random polynomial r(x) = r0 + r1 x +


+ rt?1 xt?1 , such that r(0) = r0 = L2k0 and rj 2R f0; L; : : :; 2L3n2+ tg for 1  j  t ? 1. Let P (publicly computable) be part of each share holder's key. Next, shareholder i with public

interpolation point xi = i receives secretly share si = r(xi ) 2 Z . Note, that each share is a multiple of L. Now, let  where jj = t be any subset of shareholders, observe:

d=P + zi; =

X s
z 2 Z where i i; i2 Y (x ? x )?1(0 ? x ):

v2nfig

i

v

v

(2)

over the public channel (an act which also pub0 2R licly commits to the message) ri;j 2 Z and ri;j f0; : : :; n ? 1g to server j .

Q

i;

i

 Generates ri;j 2R f0; 1; : : :; n ? 1g for j 2  nfig.  Set share to be ri;i = si
zi; ? Pj2self-held r 2 Z. i;j nfig  Privately, transmit using probabilistic encryption

(1)

Since L divides si and v2nfig (xi ? xv ) is a multiple of L, the terms in the above sum can be computed eectively over the integers from si (without multiplicative inverses) Hence to generate a signature for message m, each i 2  gives partial results ms
z  mod n, and a combining function computesQmP mod n and the nal desired result: md  mP
i2 ms
z  mod n: The above scheme is arithmetic-wise analogous to [DF91] except that it works for general RSA rather than RSA with strong primes as in [DF91], and its shared polynomial is chosen dierently. To demonstrate that sharing of points in the secret polynomial chosen as above does not leak information to t ? 1 colluding shareholders, we prove the following i

Sharing shares: Server i:

i;

Lemma 1 Let r(x) = r0 + r1x +


+ rt?1 xt?1 be a random polynomial of degree t ? 1 such that r(0) = r0 = L2k and rj 2R f0; L; : : :; L3 ng for 1  j  t ? 1. Let 0 be a set of t ? 1 servers. Then with probability at least 1 ? 2t= there exists a polynomial r0 (x) = r00 + r10 x +


+ rt0 ?1 xt?1 with r0 (0) = r00 = 0 and rj0 2 f0; L; : : :; L3 ng for 1  j  t ? 1 such that r(i) = r0 (i) for i 2 0 .

3.2 \Poly-To-Sum" share-of-shares

This protocol is executed by t servers at a time and transforms a t-out-of-l polynomial based sharing to a t-out-of-t additive sharing [F89, AGY, FGMY]. When misbehaving parties are detected the group of t active participants is changed, and the protocol restarts. The protocol provides for randomization of the current state and will augment the heuristic scheme to a secure one (in Subsection 3.3). This randomization is also designed speci cally to allow for robustness during distributed signing (as discussed in Subsection 3.4). Setup: We assume that the dealer during share distribution publishes elements g; g2 1 2 Zn of maximal order and it publishes Si = gs
L mod n for all i. Let  where jj = t be the shareholders (servers) participating in the share of shares protocol. i

 Publish Ri;j  gr

i;j

L2 g r0 , and Ui  1 i;j

Qj2 g1r0

i;j

0 0 be Verify and generate shares: Let ri;j;0 and ri;j;

the commitment values that j received privately from

i.

1. Each server j veri es that for all i 2  n fj g:

 (QSi )V1 ? (Ui?1 Qv2 Ri;v )V2Qwhere V1 = v2nfig (0 ? xv ) and V2 = v2nfig (xi ? xv ).

If the veri cation does not pass then server i is removed and new  is chosen (restart). ?

 ri;j;0  n ? 1, and gr

0 L2

i;j;

g1r

0 0 ? R

i;j;

i;j

If veri cations are disputed by j then ri;j;0 0 0 are revealed (decommitted), and and ri;j; either i or j is removed appropriately (and we restart). 2. If all veri cations pass during signing phase, shareholder's j 2  new share is s0j = ?rj00 + Pi2 ri;j;0 where rj00 = 0. (NOTE: another important usage of poly-to-sum is for the update phase in the proactivization protocol. In this case rj00 is set to satisfy: L2 divides s0j and 0  rj00 < L2 .)

Q

3. Shareholder j publishes rj00 and Qj = v2 g1r

0 0 .

v;j;

Note that the sum of the additive shares is the private key. Also note that any attempt to spoil the computation (i.e., sending information that cannot be veri ed or halting) forces an adversarial server to be removed (without opening shares of honest servers which assures maintenance of security). When the protocol is used in an environment of l  2(t ? 1) + 1 servers, we can revise the set  to a new set of t shareholders

and redo the protocol from start. After at most t-1 restart we can complete the protocol. If robustness is required before the completion of poly-to-sum a zero-knowledge proof is performed by a Prover (shareholder i) to demonstrate knowledge P 0 0 for Qi = g1R^ . The following is of R^i = v2 rv;i; performed pair-wise between servers (either trustees or at least 2t+1 servers which can vote majority). Here is a proof between one pair. Pre-Commit: At the beginning Prover for all interaction generates two new generators: g20 = grr0 ; g21 = grr1 and then proves \proof of knowledge of the discrete logarithms," Veri er then sends a bit bb and Prover sends back rrbb . The interactions between the two parties will use g2 = g21?bb . This will enable poly-time simulations of parallel commitments by the veri er. Here is how veri cation of knowledge is performed: i

1. Veri er commits to a randomly chosen h bit string c^ = c1 jj


jjch by publishing Commit = gc^g2q0 for q0 2r f0; : : : ; ng. 2. Prover transmits g2q1 ; : : : ; g2q where qi 2R f0; : : : ; 2L3n3+ t2 lt+l + lng. 3. Veri er opens commitment B1 = c^; B2 = q0 and prover veri es if gB1 g2B2 ? Commit. If veri cation fails, HALT. 4. For j = 1 : : : h, Prover transmits vj = cj R^ + qj . h

5. For j = 1 : : : h, Veri er veri es Qci g2q ? g2v j

j

j

Note that, for average-case eciency, the combiner may check, before running of the valQ Q the veri cation ues fQj gj2 , that i2 Ui = j2 Qj . Any undetected cheating will cancel. If cheating is detected, then the combiner can check each Qj individually.

Lemma 2 The poly-to-sum (PS ) protocol has the following properties:  (robustness): the protocol terminates in the pres-

ence of a (t-1)-restricted malicious adversary, and any misbehaving party deviating in its computation or communication is detected.  (correctness): Let  be the t shareholders which complete PS . Assuming the input to PS is correct polynomial shares, then the t shares s0i from  sum up to d. Furthermore, for any g 2 Zn ,

for any set of t ? 1 of these shares fi1; : : : ; it?1g of the t shareholders which complete the proto0 0 s s col, A = fg 1 ; : : : ; g ?1 j s0i1 ; : : : ; s0i ?1 ; s0i PS (si1 ; : : : ; si )g is statistically indistinguishable from B = fgr1 ; : : : ; gr ?1 j ri 2R Z(n) g.  (security): The computation of a (t-1)-restricted malicious adversary during PS is simulatable. it

i

t

t

t

t

3.3 A secure threshold RSA scheme

We now discuss a secure threshold RSA protocol. We start with the heuristic scheme of Section 3.1 (or [DF91]). The problem with proof of security is that we cannot simulate the case when the subsets of signers change from message to message. To get a provably secure protocol, the approach is to dynamically convert the signing shares of the current set of t shareholders employing the poly-to-sum technique above. Then the signing is done using the shares of the sum. By \dynamically converting" we mean that any new set of t shareholders has to go through the above poly to sum technique prior to signing. This will make partial views available to the adversary look random and independent, and will allow us to \simulate" the view available to the adversary. By demonstrating that we can simulate the view we will be able to give a proof of security. For now, we assume a static passive adversary (namely that shareholders follow the protocol). Step 0 (Setup) The share distribution protocol of Section 3.1 is performed and encryption keys for each servers are authentically and securely distributed. We assume that the dealer during setup publishes elements g; g1 2 Zn of maximal order where g1 = ga for a relatively prime to (n), (the 2elements can be part of each server's key). Si = gs
L mod n for all i is made public as well. Step 1 (Poly-to-sum): Perform the poly-to-sum (share-of-shares) protocol of Section 3.2 until a set of t servers is found who successfully complete the poly-tosum protocol without disputes. Let  be the t servers who successfully completed the protocol. Step 2 (Signing): To sign for each input message m, each server in  broadcasts partial result Sm;i; = ms0 mod n where s0i is from Section 3.2. ObQ d P serve that m  m
i2 Sm;i; mod n, where which can be easily computed by the publicly available combining function. i

i

Non-malicious shareholders in  (under passive adversary) can now sign as many messages as they desire

using the s0 shares they obtained in the poly-to-sum protocol without performing the poly to sum conversion again. As a performance optimization note that a server can keep in its cache shares for dierent 's.

Theorem 1 Assuming a (t-1)-restricted passive static adversary, the above protocol is an ecient threshold RSA scheme as secure as RSA.

3.4 Robust threshold RSA scheme

The above scheme is not robust, and in the presence of malicious adversary, a subset of size t may include up to t-1 misbehaving parties during signing and a new subset will have to be considered. Robustness provides for ecient veri cation of a shareholder's computation and implies ecient signing (it is an interactive fault detection and correction approach). Next, the protocol above is made robust: Setup: Let V erifier be the entity that computes the ecient combining function to obtain md mod n from the output of the share-holders. Let s0j be server j 's share generated from the share of share 0 proto2 col in Section 3.2 and let witness Sj0  gs
L  Q ( v2 Rv;j )=Qj be generated using public information provided in Section 3.2. Verify partial result: There is a known element of high order g and the result of the shareholder's function applied to it (which is called a \witness") [FGY]. Alternatively, a set of random elements which with high probability includes one of high order can be used, but for simplicity of presentation we assume a single element g of maximum order ((n)). An element g2 is generated by the prover in a precommit protocol described in the proof of knowledge in subsection 3.2. Then the following knowledge veri cation protocol based on [FGY], and is activated on allowed random input. We also assume that signing (i.e., step 2 in the previous section) is done by rst submitting a commitment to partial results, and then opening the commitment (this prevents any misbehaving party from correlating its share with others and implements absolute synchrony). j

0j

1. Shareholder j returns partial result Sm;j; = ms . 2. Veri er commits to a randomly chosen h bit string c^ = c1 jj


jjch by publishing Commit = gc^g2q0 for q0 2r f0; : : : ; ng. 3. Prover transmits gq1 ; : : : ; gq and mq1 ; : : : ; mq where qi 2R f0; : : :; 2L3 n3+t2 lt+l + ln2g. h

h

4. Veri er opens commitment B1 = c^; B2 = q0 and prover veri es if gB1 g2B2 ? Commit. If veri cation fails, HALT. 5. For i = 1 : : : h, Prover transmits vi = ci s0j + qi . 6. For i = 1 : : : h, Veri er veri es (Si0 )c gq ? gv and (Sm;j; )c mq ? mv . i

i

i

i

i

i

If safe primes are used, [GJKR2] may be used instead of the above since gcd(L2 ; ord(g)) = 2. Robust protocol: A combined robust protocol is comprised of an initial setup of shares distributed with published witnesses, and the protocol of Section 3.3 running with \veri cation of partial results" as above is the suggested \robust threshold RSA" (i.e., we can allow and overcome malicious static adversary).

Theorem 2 Assuming a (t-1)-restricted static malicious adversary, the above protocol is an ecient optimal-resilience robust threshold RSA scheme, which is as secure as RSA.

3.5 Size ecient shares

The previous robust schemes in [GJKR2] (based on [DDFY]), or [FGMY] had an extra order of magnitude of share size, when compared with the security parameter. Part of the reason that the above scheme has large shares is due to the need to allow share rerandomization in proactive protocols. However, when assuming a static adversary we can achieve:

Corollary 1 A \size ecient robust secure RSA function sharing" exists where a permanent share held by a shareholder is only a small constant times the secret's size (i.e. O(h)).

4 Secure Proactive RSA

4.1 \Sum-to-Poly" share of shares

The goal of this protocol is to re-share randomly the value of an additive sharing (described above) as the value of a t ? 1 degree polynomial in location 0. The protocol starts with thePparties having additive shares s0i and a public W = j2 rj00 (see Note in Step 2 of verify and generate shares in poly-to-sum). 1. Each i 2  shares its s0i (the lowest numbered member incorporates the public W into its private temporary share, i.e., s0i s0i + W for smallest i 2 ). The sharing is done Pby generating a random polynomial ri0 (x) = tv?=01 ai;v xv ,

of degree t ? 1 with zero coecient ai;0 = s0i and other coecients randomly chosen from f0; L; : : :; 2L3tn2+ g. Note that L divides all shares. 2. Server i 2  then publishes for the [F] veri 2 a
L cations all the g and privately transmits wi;j = ri0 (j ) 2 Z for j 2 f1; : : : ; lg. i;v

3. Each server j performs the following:

 Similar to [F] verify (proper share): Q gw
L2 ? tv?=01 (ga L2 )
j mod n  verify (proper secret): ga 0 L2 =? gs0 L2 i;j

i;v

v

i;

i

?

 jwi;j j  L3 t2 n2+ + 2L3 n2+t2 lt+l + ln2  L divides wi;j 4. Then dispute resolution is performed for the above Step. Complaints are sent, then faulty and corrupted system shareholders (including fault complainers) are detected. The protocol restarts from a starting point with an updated set of servers; the process repeats from the beginning until there are no disputes.

P

P

5. Now si;u = j2 wj;i = j2 rj0 (i). Erase previous history and retain new current share si;u . The gs
L2 are 2published using the multiplication mod n of gL
w . i;u

i;j

We show that:

Lemma 3 The sum-to-poly (SP ) protocol has the following properties:  (robustness): the protocol terminates in the presence of a (t-1)-restricted malicious adversary, misbehaving shareholders which deviate from the protocol are detected.

 (correctness): Let  be the t shareholders which

complete SP . Assuming the input to SP is correct sum shares, then the l shares si are a correct polynomial sharing of d which is t-wise independent.

 (security): The computation of a (t-1)-restricted malicious adversary during SP is simulatable.

4.2 The proactive protocol

We now discuss the secure proactive RSA protocol based on the sum-to-poly and the poly-to-sum protocols. Share distribution (setup): This is a setup as in the robust threshold RSA in Section 3.4: The dealer generates an RSA with public key (e; n) and private key d. It then generates shares si;0 of L2
k0 as in Section 3.1. The dealer also publishes fg; gdg for2 a g 2 Zn of maximal order and for all i the value gs 0
L mod n (actually if we have more generators, it publishes this value with respect to each of them, but to keep the exposition simple we again assume one generator). Update period: Let u u + 1. Share renewal and recovery:. The intent is to make shares at time u + 1 be t-wise independent of shares held at time u. A \poly-to-sum" share of shares protocol is performed P to create a t-out-of-t sharing of L2
k0 = W + i2 s0i where W is a public value divisible by L2 . Now the secret is additively shared, then we perform a \sum-to-poly" share-of-shares protocol. Namely, each server i shares its s0i (to deal with the public W the lowest valued server will reset s0i s0i + W ) with all servers j using polynomialinterpolation threshold scheme. Each of the l shareholders now sums up all the poly shares of each of the t share s0i generated by . Hence each shareholder will have a share of L2
k0 . Any misbehaving processor that either halts or is detected as not following the protocol is eliminated from the process and this stage restarts (from a \starting point" which is the beginning of the update period). Finally, the process ends successfully. The protocol updates all users' shares. Hence, the question whether old shares exist (renewal) or do not exist (recovery) is irrelevant since the newly dealt share becomes the mechanism by which signing is performed. The following is performed: i;

1. \starting point": The set of working t shareholders is determined. Any misbehavior or shareholder fail-stop causes a return to this stage. 2. Perform the \poly-to-sum" share-of-shares protocol (Section 3.2) with shares si;u?1 from time u ? 1 until a set of t shareholder de ned by  have no dispute and agree to shares: their respective s0i and the public W .

3. Perform the \sum-to-poly" share-of-shares protocol above. 4. After successful completion of the previous two stages the following is performed: The common \public" constants (such as the system size l, the public part of the key P , and the value of the generators) that are maintained proactively by a simple memory \refresh" procedure: each server broadcasts its current value and then the majority value becomes the new permanent value.

RSA function application period: Let time be

u. This is performed exactly as the secure threshold RSA in Section 3.3 with share si;u if robustness is not required. Otherwise perform the computation with veri cation as in the protocol of Section 3.4. We conclude that:

Theorem 3 Assuming a (t-1)-restricted mobile ma-

licious adversary, the above protocol is an ecient optimal-resilience proactive RSA scheme, which is as secure as RSA.

5 Generalized Proactive System

A general system based on extending [DDFY] to incorporate robust proactive security can be developed using the basic poly-to-sum and sum-to-poly techniques presented in this paper. A complete description will be provided in the nal paper (due to space limitations). In [DDFY], sucient conditions for sharing cryptographic functions were given. Informally (see [DDFY] for formal de nitions), they are share translation (i.e., fk1 (m)  fk2 (m) = fk1 +k2 (m)); 2) share eciency (i.e., one can compute inverses in the share space); and share simulatability (i.e., one can choose random elements in a simulatable space in a way which is indistinguishable from choosing shares in the key space). The techniques presented in [DDFY] combined with the techniques in this paper allow for proactivization of cryptographic functions which satisfy the [DDFY] conditions and in addition the following condition needed for simulation and control of growth under arithmetic operations:

De nition 2 (Ring simulatability) There exists 0 , a ring of integers which contains Zpu (domain of Zpu simulatable shares which are each of size of the security parameter). Moreover, there exists a polynomialtime (in the length) predicate, called the Mem, such that Mem(a) = True if and only if a 2 Zpu .

We now give a short description of the primary modi cations to [DDFY] in order to achieve uni ed notations with the techniques for proactive security of this paper (so that familiarity with [DDFY] will enable understanding of the basic issues herein). We rst change notation of [DDFY] slightly to simplify the discussion. Multiplication in Dq?1 (), the extended domain de ned in [DDFY], remains the same expressed as: [m0 ; : : : ; mq?2 ]  [m00 ; : : : ; m0q?2 ] = [m0  m00 ; : : : ; mq?2  m0q?2 ]. The notation for the scalar operation, however, is modi ed to [m0 ; : : : ; mq?2 ](b0 +


+b ?2 u ?2 ) . Hence the scalar operation is de ned recursively from [m0 ; : : : ; mq?2 ]b = [mb0 ; : : : ; mbq?2 ] for b 2 Z and [m0 ; : : : ; mq?2 ]u = [1; m0; : : : ; mq?3 ]  [m?q?12 ; : : : ; m?q?12 ]. To get a proactive scheme, the basic idea is to incorporate \poly-to-sum" and \sum-to-poly" into the scheme. Primarily the following changes are needed. (1) Partial signing is performed as [m; 1; : : : ; 1]s using the polynomial share si , hence, \poly-to-sum" is not necessary before partial signing since this operation is simulatable when the set of signers change. However, \poly-to-sum" is used during the proactive update phase. (2) During update, the computations are performed in the simulatable spaces; which is doable and correct due to ring simulation property and because the needed inverses are computable (share ef ciency), hence making shares divisible by L is not necessary in this case. (3) Moreover, L is not needed for simulatability because the necessary inverses are computable and therefore setting L = 1 does not prevent correctness or reduce security. (4) Also, it should be noted that it is not necessary to use unconditional commitments (in a VSS of the nature of [P91]) during \poly-to-sum" and simpler commitments (generating a scheme like [F]) are sucient. The use of [P91] was needed earlier since it was not known how to simulate the basic scheme (based on the [DF91] heuristic) to prove security. This, however, is not a problem with [DDFY], where a direct security proof exists. Finally, (5) step (3) in the verify and generate shares stage of \poly-to-sum" is not used and can be omitted. To achieve robustness during signing the witness [g; 1; : : :; 1]s is created by the dealer. There are other diculties that come into play in the creation of this scheme. For instance, when random elements are transmitted for randomization, it is necessary to know that they are of the correct form to assure correctness. Hence the Mem function is introduced to recognize domains of elements. Given all the above modi cations, the modi ed scheme achieves: q

q

i

i

Theorem 4 For any function which satis es the

share eciency, share translation, share simulatability and ring simulatability condition, there exists a secure and correct proactive threshold cryptosystem.

We can employ robust signing by using the noninteractive cryptographic program checking of [FGY], which will give a non-interactive signing stage based on availability of a random oracle (in practice, a strong cryptographic hash function). This gives:

Corollary 2 For any function which satis es the share ecient, share translation, share simulatable and ring simulatable condition, there exists a secure and correct proactive threshold cryptosystem with noninteractive signing.

6 Further Implications

Dynamic management function sharing:

Note that the poly-to-sum and sum-to-poly protocols are very exible transformations going from t-out-of-l to additive sharing t-out-of-t and back. When going back from sum sharing to polynomial sharing we can change the sharing threshold and increase the number of servers and have, say t0 -out-of-l0 (assuming, of course that at most t0 ? 1 (if t0 < t) can be corrupted at the update). Also, we can decrease the number of servers in a similar way under analogous assumptions about corrupted servers. This demonstrates the strength of this exible technique as a tool for managing a distributed function.

Flexible shared value generation:

A shared value can be rst generated in either polynomially shared or additively shared form, and then be transformed into the other form using one of \polyto-sum" or \sum-to-poly" respectively. This may ease shared generation of secrets.

Communication-sensitive adversary:

The \communication-sensitive adversary" has been dealt with in the context of protocols simulating private channels between users; our protocol uses also a public channel (the veri cation information) and we are limited to the servers outputting partial results of a given RSA function. Thus, we may need various new additional techniques to solve this technicality in the current model. One approach to dealing with such an adversary is to employ a \private channel" protocol on top of the protocol. This means that we have to send private messages to the combiner which applies the combining function. This approach fails, since everyone should be able to perform the combining function.

However, there exists a more complicated yet realistic communication model, with which we are able to neutralize the enormous power of the \communication-sensitive adversary". This is the \anonymous broadcast channel model" (in practice, re-mailing which give users \pseudonyms" exist and bulletin boards which accept messages from \pseudonyms" exist as well). The technology relies on \re-mailers" [Ch81, GT96, SR93]. The users viewing the bulletin board can relate to the message originator and messages only by the \pseudonym". This systems organization approach limits the adversary. We note that systems solutions and protocols designed against a fully-adaptive adversary are described in [FGMY-a].

Acknowledgments: We thank Tal Rabin for several important remarks on a preliminary version.

References [AGY]

N. Alon, Z. Galil and M. Yung, DynamicResharing Veri able Secret Sharing against Mobile Adversary. 3-d European Symp. on Algorithms (ESA)'95. Lecture Notes in Computer Science Vol. 979, P. Spirakis ed., SpringerVerlag, 1995, pp. 523-537. [Be] J. C. Benaloh. Secret sharing homomorphisms: Keeping shares of a secret secret. Advances in Cryptology, Proc. of Crypto'86 LNCS 263, 1987, pp. 251{260. [Bl] R. Blakley, Safeguarding Cryptographic Keys, FIPS Con. Proc (v. 48), 1979, pp. 313{317. [BF97] D. Boneh and M. Franklin, Ecient Generation of Shared RSA Keys, Crypto 97 proceedings. [B88] C. Boyd, Digital Multisignatures, IMA Conference on Cryptography and Coding, Claredon Press, 241{246, (Eds. H. Baker and F. Piper), 1986. [CH] R. Canetti and A. Herzberg, Maintaining Security in the Presence of Transient Faults, Crypto 94. [Ch81] D. Chaum, Untraceable Electronic Mail, Return Address, and Digital Pseudonym. CACM, v. 24(2) 1981, pp. 84-88. [CGMA] B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Veri able Secret Sharing and Achieving Simultaneous Broadcast, Proceedings of the 26th Symposium on Foundations of Computer Science, IEEE, 1985, pp. 335-344. [Cer] CertCo LLC, Optimal Resilience Proactive Public Key Cryptosystems, patent pending, 1997.

[DDFY] A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung, How to Share a Function Securely, ACM Proceedings of the 26th Annual Symposium on Theory of Computing, ACM, 1994, pp. 522-533. [DF89] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Advances in Cryptology { Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed., Springer-Verlag, 1989, pp. 307-315. [DF91] Y. Desmedt and Y. Frankel, Shared Generation of Authenticators and Signatures Advances in Cryptology { Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991, pp. 457-469. [DF94] Y. Desmedt and Y. Frankel, Homomorphic zeroknowledge threshold schemes over any nite Abelian group, SIAM Journal on Discrete Mathematics, 7(4), pages 667-679, November 1994. [DH] W. Die and M. Hellman, New Directions in Cryptography , IEEE Trans. on Information Theory 22 (6), 1976, pp. 644-654. [F] P. Feldman, A Practical Scheme for NonInteractive Veri able Secret Sharing, Proceedings of the 28th Symposium on Foundations of Computer Science, IEEE, 1987, pp.427-437 [F89] Y. Frankel, A practical protocol for large group oriented networks, In J. J. Quisquater and J. Vandewalle, editor, Advances in Cryptology, Proc. of Eurocrypt '89, (Lecture Notes in Computer Science 773), Springer-Verlarg, pp. 56-61. [FD-TR] Y. Frankel and Y. Desmedt, Distributed reliable threshold multisignatures, Tech. Report version TR{92{04{02, Dept. of EE & CS, Univ. of Wisconsin-Milwaukee, April 1992. (See also; Y. Frankel, Non-interactive multiparty cryptography, Phd. Thesis, UWM, 1992). [FGY] Y. Frankel, P. Gemmell and M. Yung, Witness Based Cryptographic Program Checking and Robust Function Sharing. Proceedings of the 28th Annual Symposium on Theory of Computing, ACM, 1996, pp. 499-508. [FGMY] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung. Proactive RSA, crypto 97. [FGMY-a] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung. Adaptive Adversary in Proactive PublicKey Systems, manuscript. [FY93] M. Franklin and M. Yung, Secure and Ecient O-Line Digital Money, Proc. of the 20th Int. Col. on Automata, Languages and Programming (ICALP), 1993, LNCS 700, Springer Verlag, pp. 265-276. [GHY] Z. Galil, S. Haber and M. Yung, MinimumKnowledge Interactive Proof for Decision Problems, SIAM J. Comp., 18, 1989, pp 711{739.

[GHY87] Z. Galil, S. Haber and M. Yung, Cryptographic Computations: Secure Fault Tolerant Protocols in the Public Key Model, Crypto 87, pp. 135155. [GJKR1] R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Robust Threshold DSS Signatures, Advances in Cryptology { Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996, pp. 354-371. [GJKR2] R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Robust Threshold RSA, Advances in Cryptology { Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996, pp. 157-172. [GMW] O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, Proceedings of the Nineteenth annual ACM Symp. Theory of Computing, 1987, pp 218{229. [GO] O. Goldreich and Y. Oren, De nitions and Properties of Zero-Knowledge Proof Systems, J. of Cryptology, 7(1), pp 1{32, 1994. [GM] S. Goldwasser and S. Micali, Probabilistic Encryption, J. Com. Sys. Sci. 28 (1984), pp 270299. [GMR1] S. Goldwasser, S. Micali and C. Racko, The Knowledge Complexity of Interactive ProofSystems, Siam J. on Computing, 18(1) (1989), pp. 186-208. [GT96] C. Gulcu and G. Tsudik, Mixing Email with Babel, ISOC 96. [HW] G. Hardy and E. Wright An introduction to the theory of numbers, Oxford Science Publications, London, Great Britain, fth ed., 1985 [HJKY] A. Herzberg, S. Jarecki, H. Krawczyk, M. Yung, Proactive Secret Sharing, or: how to cope with perpetual leakage, Advances in Cryptology { Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995, pp. 339-352. [HJJKY] A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, M. Yung, Proactive Public-Key and Signature Schemes Proceedings of the Fourth Annual Conference on Computer and Communications Security, ACM, 1996. [OY] R. Ostrovsky and M. Yung, How to withstand mobile virus attacks, Proc. of the 10th ACM Symposium on the Principles of Distributed Computing, 1991, pp. 51-61. [P] T.P. Pedersen, Distributed Provers with Applications to Undeniable Signatures, Advances in Cryptology { Eurocrypt 91 Proceedings, Lecture Notes in Computer Science Vol. 547, D. Davies ed., Springer-Verlag, 1991, pp. 221-242.

[P91]

[RSA] [Sh] [SR93] [Y82]

T.P. Pedersen, Non-interactive and information theoretic secure veri able secret sharing, Advances in Cryptology { Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991, pp. 129-140. R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of ACM, 21 (1978), pp. 120-126. A. Shamir, How to share a secret, Comm. of ACM, 22 (1979), pp. 612-613. D. Simon and C. Racko, Cryptographic Defense against Trac Analysis, STOC 93, pp. 672-681. A. C. Yao, Theory and Applications of Trapdoor functions, Proceedings of the 23th Symposium on the Foundation of Computer Science, 1982, pp. 80-91.