BRICS RS-00-30 Damgård & Koprowski: Practical Threshold RSA Signatures Without a Trusted Dealer BRICS

Basic Research in Computer Science

Practical Threshold RSA Signatures Without a Trusted Dealer

Ivan B. Damgård Maciej Koprowski BRICS Report Series RS-00-30 ISSN 0909-0878 November 2000 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2000, Ivan B. Damgård & Maciej Koprowski.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/00/30/

Practical Threshold RSA Signatures Without a Trusted Dealer

Ivan Damgård and Maciej Koprowski

BRICS^{⋆}, Aarhus University

Abstract. We propose a threshold RSA scheme which is as efficient as the fastest previous threshold RSA scheme (by Shoup), but where two assumptions needed in Shoup’s and in previous schemes can be dropped, namely that the modulus must be a product of safe primes and that a trusted dealer generates the keys.

1 Introduction

In a threshold public-key system we have a standard public key (for the RSA system, for instance), while the private key is shared among a set of servers, in such a way that by collaborating, these servers can apply the private key operation to a given input, to decrypt it or sign it, as the case may be. If there are l servers, such schemes typically ensure that even if an active adversary corrupts less than l/2 servers, he will not learn additional information about the private key, and will be unable to force the network to compute incorrect results. Thus threshold cryptography is an important concept because it can improve substantially the reliability and security of applications in practice of public-key systems.

Threshold schemes based on the discrete log problem are relatively straightforward to build, and have been known for a long time. It is even possible to make efficient schemes where also the key generation phase is done by the servers in a distributed way [11, 7]. This way we can completely avoid assuming any trusted parties in the system.

Basing threshold schemes on RSA is technically more difficult because we have to work in a group of non-prime and unknown order (Z_{n}^{∗} rather than a prime order subgroup of Z_{p}^{∗} for a prime p). Nevertheless RSA-based schemes have been known for some time, see [8, 12] for the first reasonably efficient and robust solutions. However, due to the technical difficulties mentioned, they tend to be more complex and less efficient in comparison to the discrete log schemes. One concrete reason is that they use secret sharing “in two levels”, i.e. server i knows a number d_{i}, such that ∑_{i} d_{i} = d, the secret RSA exponent. In addition, each d_{i} is a verifiable secret shared among the servers. In such a scenario, testing if servers have behaved correctly

⋆

Basic Research in Computer Science,

Centre of the Danish National Research Foundation.

is more complex than in the discrete log case, and if faults do occur, interaction between the servers is necessary to recover.

Recently, however, Shoup[14] proposed a threshold RSA signature scheme which is essentially as efficient as possible: the scheme uses only one level of secret sharing, to sign a message, each server simply sends a single response to a signature request, and must do work that is equivalent up to a constant factor to computing a single RSA signature. No further interaction is needed to recover from faults. Unfortunately, that scheme - like any previous efficient RSA-based scheme - needs to assume a trusted dealer to generate keys. This is caused by the fact that it relies on a special property for the RSA modulus, namely it must be the product of two so called safe primes (i.e. the modulus n is the product of primes p, q, where p′ = (p − 1)/2, q′ = (q − 1)/2 are also prime). The problem now is that although reasonably efficient distributed RSA key generation protocols are known[1, 5], none of these protocols can ensure that the modulus is a product of safe primes^{1}. One attempt to overcome this was made by Miyazaki et al. [9], who build a threshold RSA scheme that can use the key generation protocol from [5]. Unfortunately that scheme is significantly less efficient than Shoup’s. It uses two-level secret sharing and needs interaction between servers for each message signed, even if no faults occur.

In this paper, we overcome the problem in a more efficient way by constructing a new threshold RSA scheme which may be seen as a generalization of Shoup’s, is essentially as efficient as that scheme, follows the same communication pattern, but does not need the assumption about safe primes. As we shall see, this implies that the distributed RSA key generation protocol from [5] can be used to generate keys for our scheme. Note that there may be good reasons to avoid safe primes, other than the distributed key generation issue: first, we do not even know if there are infinitely many safe primes, and second it may turn out to be the case that safe primes are not ”safe” at all: although it currently looks as if safe prime products are as hard to factor as RSA moduli in general, this may eventually turn out to be false, indeed most experts agree that choosing the primes as randomly as possibly gives the best security.

On the technical level, one difficulty that arises when safe primes are not assumed, relates to the efficient zero-knowledge protocols used in [14] to verify the behavior of servers. These protocols seem to fail if safe primes are not used, primarily because the group we are working in is no longer cyclic, and may have small prime factors in its order. We get around this by showing that with small modifications to the protocols and under an appropriate intractability assumption, the adversary will not be able to exploit the “deficiencies” of the group. Concretely, we show that zeroknowledge proofs of equality of discrete logarithms over a general RSA modulus can be done very efficiently (i.e. without resorting to binary challenge proofs) as long

1 Of course, generic multiparty computation methods could be used to generate and share such keys in a distributed fashion, but this would be extremely inefficient and completely unsatisfactory in practice

as the prover does not know the factorization. This may be of independent interest, and was previously only known if the modulus was a safe prime product.

Following Shoup, we describe and prove our scheme assuming the random oracle model, however, we rely on it only for robustness of the scheme (and not for unforgeability). At the expense of an additional round of interaction when signing a message, we can avoid using random oracles. The details of this are are omitted since they are standard and straightforward.

To prove the security of our scheme, we need an intractability assumption in addition to the standard RSA assumption. Informally speaking, we assume that given the public key n, e:

– The adversary cannot compute an element a ≠ 1, −1 mod n such that a has “extremely small order”, more precisely q does not divide the order of a, where q is the largest prime factor in ϕ(n).

– The adversary cannot distinguish a random square modulo n from a random square of maximal order.

As evidence in favor of this assumption, we note that it is well known that computing the order of a random element is equivalent to factoring. Specifically w.r.t. the first item, for a random RSA modulus n, there is overwhelming heuristic evidence that the prime q will be large (superpolynomial) with overwhelming probability. And so a suitable a cannot be found by choosing randomly. Indeed, it seems that one would need to raise a randomly chosen element to the q’th power to find such an a, however, guessing q is very unlikely to be feasible if factoring is difficult at all. The second item can be seen as a generalization of the Quadratic Residuosity Assumption, which can be interpreted as stating that it is difficult to decide if a given element has a maximal power of 2 dividing its order. Our conjecture makes a similar statement for other prime factors.

For the version of our scheme we describe here, we actually need that this assumption holds, even if the adversary is given an oracle for RSA signatures, i.e. , the adversary can specify an M and will be given the e’th root modulo n of H̃(M), where H̃ is a secure hash function. While this extra condition does not seem to help the adversary in computing orders of elements, it can be removed completely if we are willing to assume that H̃ can be modelled as a random oracle.

In [3] and [6], Damgård/Jurik and Fouque et al. construct threshold versions for (generalizations of) Paillier’s probabilistic public key system [10] using the basic techniques from Shoups scheme. These protocols all assume a trusted dealer. Using similar constructions, but starting from our scheme instead of Shoup’s, threshold versions of Paillier’s scheme without a trusted dealer are easily obtained.

2 Model

Here we describe the model for threshold signature schemes we use, rather informally, due to space limitations. In the type of schemes we consider there are l servers. An honest dealer on input a security parameter k generates the public key pk and secret key shares s_{1}, ..., s_{l}, where s_{i} is sent to server number i. There is a signing protocol defined for the servers which takes a message M as input and outputs (publically) a signature σ. Finally, there is a verification predicate V, which is efficiently computable, takes pk, message M and signature σ as inputs, and returns accept or reject. Both the signing protocol and the verification predicate may make use of a random oracle.

To define security, we assume a polynomially bounded static and active adversary A, who corrupts initially t < l/2 of the l servers. Thus, the adversary always learns pk and the s_{i}’s of corrupted servers. As the adversary’s algorithm is executed, he may issue two types of requests:

– An oracle request, where he queries the random oracle used, he is then given the oracle’s answer to the query he specified.

– A signature request, where the adversary specifies a message M. This causes the signing protocol to be executed on input M, where the adversary controls the behaviour of corrupted servers (and will of course see whatever information is made public by honest servers).

At the end, A outputs a message M_{0} and a signature σ_{0}.

We say that A wins, if any of the signing requests resulted in an invalid signature being output, or if he produced a forged signature on a new message, i.e. M_{0} was not used in a previous signature request, and V (pk, M_{0}, σ_{0}) = accept.

We say that the scheme is secure, if every adversary wins with probability negligible in k^{2}.

3 The Honest Dealer Scheme

In this section we first describe our scheme assuming an honest dealer that will generate and distribute the keys. The algorithm we specify for the dealer looks rather strange, taken by itself. However, the dealer is designed in such a way that the information he distributes matches the output that can be generated by the distributed RSA key generation protocol of Frankel et al. [5]. Therefore, once we prove the secu-

2 unlike the definition in [8], we treat robustness and unforgeability together - this does not make any essential difference but is convenient for us because we prove both properties under the same intractability assumptions.

rity of the honest dealer scheme, a secure (and efficient) scheme without an honest dealer follows easily. We return to this issue in Section 5 ^{3}.

In the threshold scheme to be described, an RSA public key n, e will be selected. We will assume that there exists some method, represented by a function H̃ for mapping an input message M to an element H̃(M) ∈ Z_{n}^{∗}. Then the signature we will compute is just the standard RSA signature H̃(M)^{d} mod n, where d is the private exponent corresponding to e. We will refer to this as the underlying RSA scheme. The function H̃ can be a hash function, a redundancy scheme, or a combination of both, our construction will work fine in any case. But we do assume throughout that the underlying RSA signature scheme is secure - more precisely that it is not existentially forgeable under a chosen message attack. This is clearly a necessary assumption, since without it, no threshold scheme we build from the underlying scheme can be secure. Note that, assuming H̃ can be modelled as a random oracle, security of RSA signatures using H̃ follow from only the standard RSA assumption.

The dealer. The dealer chooses at random p_{1}, …, p_{l}, q_{1}, …, q_{l} ∈_{R} [2^{k−1}, 2^{k}] until p = (p_{1} + ⋯ + p_{l}) and q = (q_{1} + ⋯ + q_{l}) are prime numbers and gcd((p − 1)/2, Δ) = gcd((q −1)/2, Δ) = 1. The RSA modulus is n = pq. The dealer also chooses a public exponent e as a prime e > l. The public key is pk = (n, e).

Next the dealer executes generation of private keys from [5] to compute dΔ^{2} = d_{1} + ⋯ + d_{t+1} ∈ ℤ such that de ≡ 1 mod Φ(n), Δ|d_{1},…,Δ|d_{t+1} and

|d_{1}| < Cl^{l+1}Δ^{11}n^{2}, …, |d_{t+1}| < Cl^{l+1}Δ^{11}n^{2} for some constant C > 1. ^{4} The dealer performs secret sharing over the integers, which was introduced in [4]

and presented in a modified version in [5]. For 1 ≤ i ≤ t + 1 a random polynomial f_{i}(x) = ∑_{j=0}^{t} f_{i,j}x^{j} is chosen such that f_{i,0} = d_{i} and for 1 ≤ j ≤ t we have f_{i,j} ∈_{R} {0, Δ, 2Δ, …, Δ^{10}n^{2}·Δ}. We define a polynomial f(x) = f_{1}(x)+⋯+f_{t+1}(x). We can observe that f(0) = dΔ^{2}.

For 1 ≤ i ≤ l, the dealer computes s_{i} = f(i) = f_{1}(i) + ⋯ + f_{t+1}(i), which is a secret key of server i. If we define α(k, l) = 4k + (12l + 4) log l, it is easy to verify that 0 ≤ s_{i} < 2^{α(k,l)}.

The dealer chooses v ∈ Z_{n}^{∗} as a random square. For 1 ≤ i ≤ l, the dealer computes verification key v_{i} = v^{s_{i}Δ^{2}} of server i.

Signing protocol. When a message M is requested to be signed, we set x = H̃(M), where H̃ is a hash function, a redundancy scheme, or a combination of both, and use the scheme to compute x^{d} mod n.

3 We note that the description in [5] in some places leaves open alternatives for how details in their key generation protocol are executed. Choosing different options lead to minor differences in the output distribution. We stick to one option here for simplicity. Any of the other options could easily be accommodated here by adjusting the description of the honest dealer.

4 In case of a small public exponent, the protocol from [5] instead generates the private exponent dΔ^{2} as a sum of l shares. Our construction could also be based on this method. The protocol and the proofs would be analogous.

We define the signature share x_{i} of server i by

x_{i} = x^{2Δ^{2}s_{i}}.

Then the server i can prove that the discrete logarithm of x_{i}^{2} to base x̃ = x^{4Δ^{2}} is the same as the discrete logarithm of v_{i} to the base v^{Δ^{2}}.

We construct the proof of correctness. Let H be a hash function modelled as a random oracle, whose output is an L_{1}-bit integer, where L_{1} is a secondary security parameter (e.g. L_{1} = 128).

Each server i chooses at random a number r ∈ {0, …, 2^{α(k,l)+2L_{1}} − 1}. Let

c = H(v, x̃, v_{i}, x_{i}^{2}, v^{rΔ^{2}}, x^{4rΔ^{2}}), z = s_{i}c + r.

The proof of correctness produced by server i is (z, c).

To verify this proof of correctness, one should check that

c = H(v, x̃, v_{i}, x_{i}^{2}, v^{zΔ^{2}}v_{i}^{−c}, x̃^{z}x_{i}^{−2c}).

Suppose that valid shares were generated by servers from a set S = {i_{1}, …, i_{t+1}} ⊂ {1, …, l}.

For all j ∈ S we define the Lagrange coefficients multiplied by Δ:

λ_{0,j}^{S} = Δ · ∏_{i∈S\\{j\}} \frac{i}{i − j} .

Clearly the coefficients λ_{0,j}^{S} are integers and

dΔ^{3} = f(0)Δ = ∑_{j∈S} λ_{0,j}^{S}f(j) = ∑_{j∈S} λ_{0,j}^{S}s_{j}.

Therefore to combine shares, we can compute

ω = ∏_{j∈S} x_{j}^{2λ_{0,j}^{S}} = x^{4Δ^{2} ∑_{j∈S}(s_{j}λ_{0,j}^{S})} = x^{4Δ^{5}d}.

We can observe that

ω^{e} = x^{4Δ^{5}}.

Since e is prime to 4Δ^{5}, we can obtain such integers a and b from the extended Euclidian algorithm that a4Δ^{5} + be = 1. Finally we have a signature y = w^{a}x^{b}, because

y^{e} = (ω^{a}x^{b})^{e} = x.

This shows that y is obtained if the signature shares x_{i} are computed by honest servers only. In real life, we will only know that the x_{i}’s are values that allow the servers to produce acceptable proofs of correctness. We will later show that this (with overwhelming probability) is sufficient.

4 Proof of Security for the honest Dealer Scheme

We start by stating our intractability assumption more formally. To this end, we define a signing oracle O(n, e, H̃) to be an oracle that on input a message M returns the signature H̃(M)^{d} mod n.

Conjecture 1. – Consider any probabilistic polynomial time algorithm who gets as input n, e (as chosen by the honest dealer on input k), gets access to a signing oracle O(n, e, H̃), and outputs a number a. For any such algorithm, the probability that a ≠ 1, −1 mod n and q does not divide the order of a, where q is the largest prime factor in ϕ(n), is negligible in k.

– Let D = {D(k)| k = 1, 2..} be the family of distributions where D(k) is the distribution of n, e, v generated by our honest dealer on input k. Define D′ to be the same, except that v is chosen as a random square of maximal order. Then D and D′ are polynomial time indistinguishable, where distinguishers are given access to a signing oracle O(n, e, H̃).

This assumption was already discussed in the introduction. Note that if we are willing to assume that H̃ can be modelled as a random oracle, then the signing oracles can be removed from the conjecture by a standard argument^{5}.

A number of preliminary observations:

Lemma 1. The proofs of correctness for signature shares produced by honest servers can be simulated with a statistically close distribution, given the public key and the message to be signed.

Proof. We construct a simulator which can simulate the proof of correctness generated by server i without knowing the value of secret s_{i}. Recall that we invoke the random oracle for the hash function H. The simulator controls the random oracle. Whenever the adversary queries the random oracle, if it has not been defined yet at the given point, the simulator picks a random value and sends it to the adversary. When a honest server is expected to produce a proof of correctness for given x, x_{i}, the simulator picks random c′ ∈ {0, …, 2^{L_{1}} − 1} and z′ ∈ {0, …, 2^{α(k,l)+2L_{1}} − 1}. The value of the random oracle at (v, x̃, v_{i}, x_{i}^{2}, v^{z′Δ^{2}}v_{i}^{−c′}, x̃^{z}x_{i}^{−2c′}) is declared to be c′. With overwhelming probability, the random oracle has not been defined at this point before. The simulated proof is (z′, c′). The only difference to a real proof (z, c) is that in a real execution, we have z = r + cs_{i}, where r is a random α(k, l) + 2L_{1}-bit number. But since r and z′ are L_{1} bits longer than cs_{i}, the distance between the distributions of z and z′ is exponentially small in L_{1}. □

5 Since under this assumption, a signing oracle is easy to implement: if the adversary wants to see a signature on message M, choose a random σ ∈ Z_{n}^{∗}, define the output of H̃ on input M to be σ^{e} mod n, so that σ now is the signature on M

Lemma 2. Let q be the largest prime factor in ϕ(n), and consider a signature share x_{i} (for an input x) produced by a corrupt server. Assume that the element v produced by the honest dealer has maximal order (among all squares modulo n), and that x_{i} is incorrect, i.e., x_{i}^{2} ≠ (x^{4Δ^{2}})^{s_{i}} mod n. Then, either q does not divide the order of x_{i}^{2}·(x^{4Δ^{2}})^{−s_{i}} mod n, or the probability that the adversary can construct an acceptable proof of correctness for x_{i} is negligible. Furthermore, a correct signature can be computed from t + 1 correct signature shares.

Proof. Let (z, c) be an acceptable proof produced by a corrupt server i. Therefore

c = H(v, x̃, v_{i}, x_{i}^{2}, v^{zΔ^{2}}v_{i}^{−c}, x̃^{z}x_{i}^{−2c}).

We can reinterpret this proof as an application of the following interactive protocol, where the verifier is replaced by a call to the random oracle:

Let G be a group of squares in ℤ_{n}^{∗}. We have elements ṽ, w = v^{s} ∈ G, where ṽ has maximal order in G and the prover knows s. The prover P makes elements α, β, guaranteed to be in G as well, and wants to convince us that α^{s} = β.

So α, β, ṽ correspond to x̃, x_{i}^{2}, v^{Δ^{2}} above. Note that if v has maximal order, so does v^{Δ^{2}}, since n was chosen such that G has order prime to Δ.

The prover performs the following steps:

1. P chooses r in some large enough interval and sends a = ṽ^{r}, b = α^{r}.

2. P gets a random challenge c from the verifier.

3. P replies by sending z = r + cs

4. To check the proof, one verifies that ṽ^{z} = aw^{c} and α^{z} = bβ^{c}.

We can always write G = G_{1} ×..×G_{u}, where the order of G_{j} is a power of q_{j} and q_{1},…,q_{u} are the distinct prime factors in the order of G. So then we can think of α as a u-tuple, α = (α_{1}, ..., α_{u}), α_{j} ∈ G_{j}, and similarly for the other group elements. Now, of course, α^{s} = β iff α_{j}^{s} = β_{j} for all j.

Claim. If for some j, α_{j}^{s} ≠ β_{j}, then for any initial message (a, b) in the protocol, there is at most one value of c mod q_{j}, for which a satisfactory reply z to c exists.

To prove this, there are two cases we must look at, depending on whether β_{j} ∈< α_{j} > or β_{j} ∉< α_{j} >.

Assume first that β_{j} ∉< α_{j} >. Suppose that for some initial message a, the prover can answer both c and c′, where c ≠ c′ mod q_{j}. This means that the prover can send z and z′ such that α_{j}^{z} = bβ_{j}^{c} and α_{j}^{z′} = bβ_{j}^{c′}. Dividing one equation by the other we get α_{j}^{z′−z} = β_{j}^{c′−c}. Since we assumed that β_{j} ∉< α_{j} >, it must be the case that < β_{j} > ∩ < α_{j} > is a proper subgroup of < β_{j} >. Hence the order of β_{j}^{c′−c} must be strictly smaller than the order of β_{j}, but this is a contradiction since c − c′ is relatively prime to q_{j} by assumption.

Next, assume that β_{j} = αs̃ ; j for some s̃, but nevertheless β_{j} ≠ α_{j}^{s}. So s̃ ≠ s mod ord(α_{j}), where ord(α_{j}) is some power of q_{j}. If we let q_{j}^{ν_{j}} be the order of ṽ_{j}, we have ord(α_{j}) ≤ q_{j}^{ν_{j}} because ṽ has maximal order in G. Assume again that given some initial message a, the prover can answer both c and c′, where c ≠ c′ mod q_{j}, by sending responses z, z′. From the equations the verifier checks, we get

ṽ_{j}^{z′−z} = w_{j}^{c′−c}, α_{j}^{z′−z} = β_{j}^{c′−c}

Now, c′ − c is relatively prime to q_{j}, we can set d = (c′ − c)^{−1} mod q_{j}^{ν_{j}} and raise both equations to the d’th power. Since the order of α_{j} - and hence of β_{j} - is at most q_{j}^{ν_{j}}, this gives us

ṽ_{j}^{d(z′−z)} = w_{j}, α_{j}^{d(z′−z)} = β_{j}

Hence d(z − z′) = s mod ord(ṽ_{j}) and also d(z − z′) = s̃ mod ord(α_{j}), which implies s = s̃ mod ord(α_{j}), a contradiction.

This finishes the proof of the claim.

We now return to the situation where we have given an incorrect signature share x_{i}. Recall that we defined q to be the largest prime factor in the order of Z_{n}^{∗}, and hence in the order of G, so q is one of the q_{j}’s, say q = q_{1}. Let ϕ be the natural homomorphism from G to G_{1}. We may assume that ϕ(x_{i}^{2}) ≠ ϕ((x^{4Δ^{2}})^{s_{i}}), i.e., x_{i} is “ incorrect in G_{1}”, since otherwise q does not divide the order of x_{i}^{2}(x^{4Δ^{2}})^{−s_{i}}. It then follows from the claim we just proved that for each oracle call the adversary makes where x_{i} occurs as signature share, the probability that this results in an acceptable proof is at most 1/q. (note that if the adversary attempts to make a proof without calling the oracle it is clear that it will be accepted with probability at most 2^{−L_{1}}). It follows from the first part of conjecture 1 that 1/q must be negligible, since otherwise a small order element could be found by guessing at random. Since the adversary can only make a polynomial number of oracle calls, it follows that the probability that he can make an acceptable proof for such an x_{i} is negligible.

Combining shares. Assume that we have t + 1 correct signature shares x′_{i_{1}}, …, x′_{i_{t+1}}. For 1 ≤ j ≤ t + 1 the signature shares satisfy a property

x′_{i_{j}} = x̃^{s′_{i_{j}}} , where s′_{i_{j}} ≡ s_{i_{j}} mod ord(v^{Δ^{2}}).

Since v is an element of maximal order in the group of squares in ℤ_{n}^{∗} and x̃ = x^{4Δ^{2}}, we have

x′_{i_{j}} = x̃^{s′_{i_{j}}} = x̃^{s_{i_{j}}} mod n.

Therefore t + 1 correct signature shares allow us to compute a correct signature. □

Lemma 3. Let n, e, distributed as the honest dealer chooses them, be given. Based on this, the information the adversary learns from the honest dealer initially can be simulated with a statistically close distribution.

Proof. Suppose that the adversary corrupted t servers i_{1}, …, i_{t}.

We choose at random r ∈ ℤ_{ln} and distribute rΔ^{2} randomly as a sum rΔ^{2} = r_{1}+⋯+r_{t+1}, where Δ|r_{1},…,Δ|r_{t+1} and |r_{1}| < Cl^{l+1}Δ^{11}n^{2}, …, |r_{t+1}| < Cl^{l+1}Δ^{11}n^{2}. We perform secret sharing over the integers to share r. For 1 ≤ i ≤ l a random polynomial g_{i}(x) = ∑_{j=0}^{t} g_{i,j}x^{j} is chosen such that g_{i,0} = r_{i} and for 1 ≤ j ≤ t we have g_{i,j} ∈_{R} {0, Δ, …, Δ^{10}n^{2}·Δ}. We define a polynomial g(x) = g_{1}(x)+⋯+g_{t+1}(x). We can observe that g(0) = rΔ^{2}.

The function g gives us a polynomial sharing over the integers of r, which was generated like in the sum-to-poly protocol [4] and by Lemma 3 from [4] it is almost t-wise independent. Since the adversary learns t shares s_{i_{1}} = (f_{1} + ⋯ + f_{t+1})(i_{1}), …, s_{i_{t}} = (f_{1} + ⋯ + f_{t+1})(i_{t}), he can not distinguish these shares from random values and from the shares generated for him by the honest dealer.

Let w be a random square in ℤ_{n}^{∗}. We define the verification key v = w^{e} mod n. The verification key of a corrupted server i is v_{i} = v^{s_{i}Δ^{2}}. For an uncorrupted

server i, we define set S = {0, i_{1}, …, i_{t}}. We can take the normal Lagrange coefficients and multiply them by Δ so they become integers. The results are called λ_{i,j}^{S} and we have

Δf(i) = ∑_{j∈S} λ_{i,j}^{S}f(j).

Since the adversary can not distinguish our secret d from r, we can compute

v_{i} = v^{s_{i}Δ^{2}} = v^{Δ(dΔ^{2}λ_{i,0}^{S}+λ_{i,i_{1}}^{S}s_{i_{1}}+···+λ_{i,i_{t}}^{S}s_{i_{t}})}
= w^{Δ(Δ^{2}λ_{i,0}^{S}+e(λ_{i,i_{1}}^{S}s_{i_{1}}+···+λ_{i,i_{t}}^{S}s_{i_{t}}))} mod n.

The adversary’s view consists from n, e, s_{i_{1}}, …, s_{i_{t}}, v, v_{1}, …, v_{l}. Since it was generated on the basis of the adversary’s shares s_{i_{1}}, …, s_{i_{t}}, which were statistically indistinguishable from the adversary’s shares produced by the honest dealer, the adversary can not distinguish this view from the one given by the honest dealer. □

Lemma 4. Assume we are given a set of values distributed by the honest dealer to the adversary, i.e., n, e, v, v_{1}, v_{2}, ..., v_{l} and the s_{i}’s sent to the corrupt servers. Let also a message M, and the signature H̃(M)^{d} mod n be given. Based on this, the contributions from honest servers in the protocol where M is signed can be simulated with the correct distribution.

Proof. Let {i_{1}, …, i_{t}} be the set of corrupted servers. Let y ≡ H̃(M)^{d} mod n and x ≡ y^{e} ≡ H̃(M) mod n.

We define set S = {0, i_{1}, …, i_{t}}. We can take the normal Lagrange coefficients and multiply them by Δ so they become integers. We can easily compute x_{i} = x^{2Δ^{2}s_{i}} for an uncorrupted player i as

x_{i} = y^{2Δ(Δ^{2}λ_{i,0}^{S}+e(λ_{i,i_{1}}^{S}s_{i_{1}}+···+λ_{i,i_{t}}^{S}s_{i_{t}}))} mod n.

□ 4.1 Proof assuming v has Maximal Order

As a first step, we prove:

Lemma 5. Modify the honest dealer scheme described above such that the honest dealer chooses v to be a random element of maximal order (among the squares modulo n). Then the resulting scheme is secure under Conjecture 1 and assuming the underlying standard RSA signature scheme is secure.

Proof. Assume we are given an adversary A that breaks the scheme, with probability at least 1/p(k), for some polynomial p(). We will then build an algorithm that with approximately the same probability either breaks the first part of Conjecture 1 or the underlying RSA scheme. So our algorithm gets n, e as input, and also gets a chosen message attack on the underlying RSA scheme, i.e., access to an oracle which on input M returns H̃(M)^{d} mod n. The algorithm now behaves as follows:

1. Invoke Lemma 3 to generate from n, e a simulation of the honest dealer (note that this produces a random square v which does not necessarily have maximal order - we deal with this problem below). Send the data produced to A.

2. For every oracle request A issues, check if the input value to the oracle that A specified has been asked for before. If so, return the same answer that was returned earlier. Otherwise, return a fresh random value as an answer and record this value.

3. For every signature request (say, on message M) A issues, call the oracle to obtain the signature H̃(M)^{d} mod n. Use this and the data generated in step 1 to invoke Lemma 4 and compute the contributions from honest servers in the signing protocol where M is the input. Invoke Lemma 1 to simulate the proofs of correctness from honest players. Send all data produced in this step to A, and receive signature shares x_{i} and proofs for the corrupt servers from A.

4. If A produces an incorrect signature share x_{i} and an acceptable proof for this share, stop and output x_{i}^{2} · (x^{4Δ^{2}})^{−s_{i}} mod n (where x = H̃(M) and M is the message that was signed).

5. If A stops and outputs M_{0}, σ_{0}, output this pair and stop.

To analyze this algorithm, note first that the simulation of the honest dealer in step 3 produces v as a random square, where the honest dealer we have assumed in this subsection chooses v as a random square of maximal order. However, for any prime p, there is a non-negligible probability that a randomly chosen number modulo p has maximal order, namely p − 1 (see [13]). This (and the Chinese Remainder Theorem) implies that if we let GOOD be the event that v is a square of maximal order, there is a non-negligible probability that GOOD occurs. It will therefore be sufficient to show that the probability that our algorithm breaks one of the two assumptions, given that GOOD occurs, is non-negligible.

Under this assumption, step 3 simulates our honest dealer with a statistically close distribution. Therefore, the simulations of the signing protocols are also statistically close to the real life distributions (by Lemma 4 and 1). The simulation of the random oracle is trivially perfectly indistinguishable from the real thing. It follows that the probability that A breaks the threshold signature scheme during our simulation is equal to the probability with which this happens in real life except for a negligible amount, and certainly is at least 1/p′(k) for some polynomial.

However, assume first that A does this by producing an incorrect signature share x_{i} and a valid proof for it (by Lemma 2 this is necessary to make the signing protocol output a bad signature). By Lemma 2, this means that x_{i}^{2}·(x^{4Δ^{2}})^{−s_{i}} mod n has order not divisible by q, except with negligible probability, and so we have broken the first part of Conjecture 1. On the other hand, if M_{0} did not occur in any of A’s signature requests, it did not occur in any of ours either, so if also σ_{0} = H̃(M_{0})^{d} mod n, i.e., is a valid signature, we have broken the underlying RSA signature scheme.

4.2 Proof in General

We are now ready for the main result:

Theorem 1. Consider the original honest dealer scheme described above where the honest dealer chooses v to be a random square modulo n. This scheme is secure under Conjecture 1 and assuming the underlying standard RSA signature scheme is secure.

Proof. Assume the result is false, i.e. there exists an adversary A that breaks the scheme with significant probability. We will then argue that this leads to a contradiction with the second part of Conjecture 1. So let us assume that we are given values n, e, v. We know that n, e are chosen as the honest dealer would choose them, and we will show how to use the assumed adversary A to decide if v is a random square or a square of maximal order.

Note first that we may as well try to decide if v^{e} mod n is random or of maximal order, since raising to the e’th power preserves order and is a 1-1 mapping. So by replacing v by v^{e} mod n, we see that we may assume without loss of generality that we know the e’th root of v. With this in mind, a trivial modification of Lemma 3 shows how the honest dealer can be simulated given n, e and v (and the e’th root of v).

We now run the simulation algorithm that appears in the proof of Lemma 5, with two changes:

– In step 1, we run the modified simulation of the honest dealer we just described.

– Having finished, we output v is random if A broke the threshold signature scheme, and v has maximal order otherwise.

It is evident from this description that if v has maximal order, we will be producing a simulation that is statistically close to the view of A attacking the scheme with maximal order v, and similarly for random v. It now follows that if v is in fact random, we will output v is random with probability at least 1/p(k) for some polynomial p(), by assumption on A, while this happens with negligible probability if v has maximal order, by Lemma 5.

5 Removing the Honest Dealer

By inspection, it is straightforward to check that the output data from the distributed key generation protocol of [5] matches the data we have assumed that the trusted dealer generates, with one exception : we have required that n is such that ϕ(n)/4 is not divisible by any prime less than l, and this condition is not automatically satisfied using [5].

This is easily handled, however: the protocol from [5] contains a test division step where each candidate p for a prime factor in n is testdivided by small prime factors. At this point, p is shared additively among the players, so it is trivial to obtain an additive sharing of p − 1, and testdivide p − 1 by all primes less than l. This will of course slow down the protocol because more candidates will be rejected, however, by Mertens’ theorem the cost will only be a factor proportional to log l.

To show security of the combined scheme, we assume (for concreteness) that the protocol from [5] according to the definition of Canetti [2] is a secure protocol for computing the function F, which on input the security parameter k outputs to all players the values n, e, v, {v^{s_{i}} mod n}, and s_{i} as private output to server i^{6}. Security of the entire combined scheme now follows from Canetti’s composition theorem, provided we show that our protocol is secure given an “ideal implementation” of F, i.e., an oracle that on input k outputs to all players a set of output values for F chosen according to the correct distribution. But since such an oracle is equivalent to an honest dealer, the required proof is precisely what we have given in the previous sections.

6 Efficiency Analysis

It is straightforward to check that the number of bits sent by each server in order to sign a message, as well as the number of modular multiplications the server needs to perform, is proportional to the bit length of its share s_{i} of the secret key. From the estimates on s_{i} in Section 3 it therefore follows that the communication complexity per server is O(k + l log l) bits and the computation is O(k + l log l)

6 [5] does not directly reference the definition of [2]. Nevertheless, the simulation based security proof they give fits with Canetti’s definition

modular multiplications, where l is the number of servers and k is the length of the modulus.

This is more than in Shoups[14] scheme which has complexity O(k), however, in practice k must be 1000 or more for security reasons, while l is going to be much smaller, so this difference is hardly significant in practice. In the hidden constants, the main difference is a factor of 2 in Shoup’s favor. As a concrete example, for a 1000 bit modulus and 32 servers, Shoups scheme will have shares of size 1 Kbit while our shares will be about 4 Kbits.

References

1. D. Boneh and M. Franklin Efficient generation of shared RSA keys, Proc. of Crypto’ 97, Springer-Verlag LNCS series, nr. 1233.

2. R. Canetti, Security and Composition of Multiparty Cryptographic Protocols, Journal of Cryptology, vol.13, 2000. On-line version at http://philby.ucsd.edu/cryptolib/1998/98-18.html.

3. Damgård and Jurik: A Generalization and some Applications of Paillier’s Probabilistic Public-key System, to appear in Public Key Cryptography 2001.

4. Yair Frankel, Peter Gemmell, Philip D. MacKenzie and Moti Yung Optimal-Resilience Proactive Public-Key Cryptosystems Proc. of FOCS 97.

5. Yair Frankel, Philip D. MacKenzie and Moti Yung Robust Efficient Distributed RSA-Key Generation, Proc. of STOC 98.

6. P. Fouque, G. Poupard, J. Stern: Sharing Decryption in the Context of Voting or Lotteries, Proceedings of Financial Crypto 2000.

7. Gennaro, Jarecki, Krawczyk and Rabin: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, Proc. of EuroCrypt 99, Springer Verlag LNCS series, nr. 1592.

8. Gennaro, Rabin, Jarecki and Krawczyk: Robust and Efficient Sharing of RSA Functions, J.Crypt. vol.13, no.2.

9. Shingo Miyazaki, Kouichi Sakurai and Moti Yung On Threshold RSA-Signing with no Dealer, Proc. of ICISC 1999, Springer Verlag LNCS series, nr.1787.

10. P.Pallier: Public-Key Cryptosystems based on Composite Degree Residue Classes, Proceedings of EuroCrypt 99, Springer Verlag LNCS series, pp. 223-238.

11. Pedersen: A Threshold cryptosystem without a trusted third party, proc. of EuroCrypt 91, Springer Verlag LNCS nr. 547.

12. T.Rabin: A Simplified Approach to Threshold and Proactive RSA, proc. of Crypto 98, Springer Verlag LNCS 1462.

13. J. B. Rosser and L. Schoenfeld: Approximate formulas for some functions of prime numbers, Ill. J. Math. 6 (1962), 64–94.

14. Victor Shoup Practical Threshold Signatures, Proceedings of EuroCrypt 2000, Springer Verlag LNCS series nr. 1807.

Recent BRICS Report Series Publications

RS-00-30 Ivan B. Damgård and Maciej Koprowski. Practical Threshold RSA Signatures Without a Trusted Dealer. November 2000. 14 pp.

RS-00-29 Luigi Santocanale. The Alternation Hierarchy for the Theory of μ-lattices. November 2000. 44 pp. Extended abstract appears in Abstracts from the International Summer Conference in Category Theory, CT2000, Como, Italy, July 16–22, 2000.

RS-00-28 Luigi Santocanale. Free μ-lattices. November 2000. 51 pp. Short abstract appeared in Proceedings of Category Theory 99, Coimbra, Portugal, July 19–24, 1999. Full version to appear in a special conference issue of the Journal of Pure and Applied Algebra.

RS-00-27 ZoltánÉsik and Werner Kuich. Inductive^{∗}-Semirings. October 2000. 34 pp.

RS-00-26 František Čapkovič. Modelling and Control of Discrete Event Dynamic Systems. October 2000. 58 pp.

RS-00-25 Zoltán Ésik. Continuous Additive Algebras and Injective Simulations of Synchronization Trees. September 2000. 41 pp.

RS-00-24 Claus Brabrand and Michael I. Schwartzbach. Growing Languages with Metamorphic Syntax Macros. September 2000.

RS-00-23 Luca Aceto, Anna Ingólfsdóttir, Mikkel Lykke Pedersen, and Jan Poulsen. Characteristic Formulae for Timed Automata. September 2000. 23 pp.

RS-00-22 Thomas S. Hune and Anders B. Sandholm. Using Automata in Control Synthesis — A Case Study. September 2000. 20 pp. Appears in Maibaum, editor, Fundamental Approaches to Software Engineering: First International Conference, FASE ’00 Proceedings, LNCS 1783, 2000, pages 349–362.

RS-00-21 M. Oliver Möller and Rajeev Alur. Heuristics for Hierarchical Partitioning with Application to Model Checking. August 2000. 30 pp.

RS-00-20 Luca Aceto, Willem Jan Fokkink, and Anna Ingólfsdóttir. 2-Nested Simulation is not Finitely Equationally Axiomatizable. August 2000. 13 pp.