BRICS RS-00-5 Damgård & Jurik: Efficient Protocols based on Probabilistic Encryption BRICS

Basic Research in Computer Science

Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes

Ivan B. Damgård Mads J. Jurik

BRICS Report Series RS-00-5 ISSN 0909-0878 March 2000 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2000, Ivan B. Damgård & Mads J. Jurik.

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/5/

Efficient Protocols based on Probabilistic Encryption using

Composite Degree Residue Classes

Ivan B. Damgård and Mads J. Jurik

Aarhus University, BRICS^{⋆} (preliminary version)

Abstract. We study various applications and variants of Paillier’s probabilistic encryption scheme. First, we propose a threshold variant of the scheme, and also zero-knowledge protocols for proving that a given ciphertext encodes a given plaintext, and for verifying multiplication of encrypted values. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits. Finally, we propose a variant of the encryption scheme, that allows reducing the expansion factor of Paillier’s scheme from 2 to almost 1.

1 Introduction

In [7], Paillier proposes a new probabilistic encryption scheme based on computations in the group Z_{n^{2}}^{∗}, where n is an RSA modulus. This scheme has some very attractive properties, in that it is homomorphic, allows encryption of many bits in one operation with a constant expansion factor, and allows efficient decryption. In this paper we propose some tools for applications of this scheme and some variants making it suitable for additional applications.

We propose a threshold variant of Pallier’s scheme, allowing a number of servers to share knowledge of the secret key, such that

⋆

Basic Research in Computer Science, Centre of the Danish National Research Foundation.

any large enough subset of them can decrypt a ciphertext, while smaller subsets have no useful information. It is straightforward to apply known techniques for threshold RSA (such as [8]) to Pallier’s scheme as it was originally described. However, doing this would lead to an insecure scheme as we explain later. We present a modification of Pallier’s decryption algorithm that solves this problem. In work independent from, but earlier than ours, Fouque, Poupard and Stern [4] propose the first threshold variant of Pallier’s scheme. Their basic idea is very similar to ours, with only minor technical differences making our decryption algorithm slightly simpler (as detailed later).

We also propose a zero-knowledge proof of knowledge allowing a prover to show that a given ciphertext encodes a given plaintext. From this we derive other tools, such as a protocol showing that a ciphertext encodes one out of a number of given plaintexts. Finally, we propose a protocol that allows verification of multiplicative relations among encrypted values without revealing extra information.

We look at applications of this to electronic voting schemes. A large number of such schemes is known, but the most efficient one, at least in terms of the work needed from voters, is by Cramer, Gennaro and Schoenmakers [3]. This protocol provides in fact a general framework that allows usage of any probabilistic encryption scheme for encryption of votes, if the encryption scheme has a set of ”nice” properties, in particular it must be homomorphic. The basic idea of this is straightforward: each voter broadcasts an encryption of his vote (by sending it to a bulletin board) together with a proof that the vote is valid. All the valid votes are then combined to produce an encryption of the result, using the homomorphic property of the encryption scheme. Finally, a set of trustees (who share the secret key of the scheme in a threshold fashion) can decrypt and publish the result.

Paillier pointed out already in [7] that since his encryption scheme is homomorphic, it may be applicable to electronic voting. In order to apply it in the framework of [3], however, some important building blocks are missing: one needs an efficient proof of validity of a vote, and also an efficient threshold variant of the scheme, so that the result can be decrypted without allowing a single entity the possibility of learning how single voters voted^{1}.

These building blocks are precisely what we provide here. Thus we immediately get a voting protocol. In this protocol, the work needed from the voters is of the same order as in the original version of [3]. However, the work needed to produce the result is reduced dramatically, as we now explain. With the El Gamal encryption used in [3], the decryption process after a yes/no election produces g^{R} mod p, where p is prime, g is a generator and R is the desired result. Thus one needs to solve a discrete log problem in order to find the result. Since R is bounded by the number of voters M, this is feasible for moderate size M’s. But it requires Ω(\sqrt{M}) exponentiations, and may certainly be something one wants to avoid for large scale elections. The problem becomes worse, if we consider an election where we choose between L candidates, L ≥ 2. The method given for this in [3] is exponential in L in that it requires time Ω(\sqrt{M}^{L−1}), and so is prohibitively expensive for elections with large L.

In the scheme we propose below, this work can be removed completely. Our decryption process produces the desired result directly. We also give ways to implement efficiently constraints on voting that occur in real elections, such as allowing to vote for precisely t out of the L candidates, or to vote for up to t of them. The complexity of this scheme is linear in L. We propose a particularly efficient variant of 1 out of L voting which is some cases will produce votes of length O(log L) bits. This is optimal up to a constant factor, since with less than log L bits one cannot distinguish between the L candidates. Furthermore this scheme requires only 1 decryption operation, even when L > 2.

In [6], Hirt and Sako propose a general method for building receipt-free election schemes, i.e. protocols where vote-buying or - coercing is not possible because voters cannot prove to others how they voted. Their method can be applied to make a receipt-free version of the scheme from [3]. It can also be applied to our scheme, with the same efficiency gain as in the non-receipt free case.

1 In [4], voting was also pointed out as a potential application, but no suggestion was made there for a proof of validity of a vote.

Finally, we propose a variant of the encryption scheme, that allows reducing the expansion factor of Paillier’s scheme from 2 to almost 1.

2 Paillier’s Probabilistic Encryption Scheme

For completeness, we recall here briefly Paillier’s scheme, please refer to [7] for proofs of the claims we make here.

Paillier’s scheme starts from the observation that if n = pq, p, q odd primes, then Z_{n^{2}}^{∗} as a multiplicative group is a direct product G × H, where G is cyclic of order n and H is isomorphic to Z_{n}^{∗}. Thus, the factor group Ḡ = Z_{n^{2}}^{∗}/H is also cyclic of order n. For an arbitrary element a ∈ Z_{n^{2}}^{∗}, we let ā = aH denote the element represented by a in the factor group Ḡ.

It turns out that the element \overline{1 + n} := (1 + n)H ∈ Ḡ is a generator, and moreover (1 + n)^{i} = 1 + in mod n^{2}. Hence the cosets of H in Z_{n^{2}}^{∗} are

H, (1 + n)H, (1 + 2n)H, ..., (1 + (n − 1)n)H.

This gives a natural numbering of these cosets.

Let λ be the least common multiple of p−1 and q−1, thus raising to exponent λ in Z_{n}^{∗} always gives 1. Then if for some element a is in the i’th coset, or in other words ā = \overline{1 + n}^{i}, then for some element in h ∈ H it holds that a = (1 + n)^{i}h mod n^{2}, and so

a^{λ} = ((1 + n)^{i}h)^{λ} = 1 + (iλ mod n) · n mod n^{2}

If we define the function L() as L(b) = (b − 1)/n, we get that

L(a^{λ}) = λi mod n

So knowledge of the factors of n, and hence of λ, allows to compute discrete logarithms to the base \overline{1 + n} in Ḡ. Clearly, if we have another generator ḡ of Ḡ, where ḡ = \overline{1 + n}^{j} then for arbitrary a, we have for some x ∈ Z_{n}

a = ḡ^{x} = \overline{1 + n}^{jx}

and so discrete logarithms to base ḡ can be computed by computing first the discrete log base \overline{1 + n}, and then multiplying by j^{−1} mod n.

Paillier’s public key system now uses n, g as public key, where g is a random number modulo n^{2}, chosen such that ḡ generates Ḡ. The secret key is λ. To encrypt a number i ∈ Z_{n}, one chooses a random r ∈ Z_{n^{2}}^{∗}, and sends

E(i, r) = g^{i}r^{n} mod n^{2}

From the structure of the group we are in, it is clear that r^{n} mod n^{2} is a random element in H, and so E(i, r) is a random element with the property that \overline{E(i, r)} has discrete log i to the base ḡ in Ḡ.

By what we said above, it is now clear that the receiver who knows λ can compute i as

i = L(E(i, r)^{λ} mod n^{2}) · L(g^{λ} mod n^{2})^{−1} mod n

This system relies for security on the difficulty of distinguishing random elements in different cosets of H, it is semantically secure, if it is hard to decide if two given elements are in the same coset. This problem is at most as hard as factoring n, but we do not know much else about it. We hope that our results will motivate further study of it.

3 Some Building Blocks

3.1 A Threshold Variant of the Scheme

What we are after in this section is a way to distribute the secret key to m servers, such that any subset of at least t of them can do decryption efficiently, while less than t have no useful information. Of course this must be done without degrading the security of the system.

In [8], Shoup proposes an efficient threshold variant of RSA signatures. The main part of this is a protocol that allows a set of servers to collectively and efficiently raise an input number to a secret exponent modulo an RSA modulus n. A little more precisely: on input a number a, each server returns a share of the result, together with a proof of correctness. Given sufficiently many correct shares, these can be efficiently combined to compute a^{d} mod n, where d is the secret exponent.

As we explain below it is quite simple to transplant this method to our case, thus allowing the servers to raise to a secret exponent modulo n^{2}. It now may seem easy to solve our problem: We first let the servers help us compute E(i, r)^{λ} mod n^{2} and g^{λ} mod n^{2}, then the remaining part of the decryption is easy to do without knowledge of λ.

However, the natural goal for a threshold version of an encryption scheme is, informally speaking, to be as secure as the original scheme. Unfortunately the simple idea we just described is completely insecure under a chosen ciphertext attack. In such an attack, E(i, r)^{λ} mod n^{2} will become known to the adversary. Now, if he submits as ciphertext a number of form (1 + n)^{i}r^{n} mod n^{2}, then he will learn λi mod n, he can divide out i to learn λ, and the system is completely broken. Applying the same attack to Pallier’s original system does not lead to a similar disaster: it is easy to see that attacker would learn the discrete log of ḡ base \overline{(1 + n)}, but it is not at all clear that this would enable him to find the secret key. If we restrict to attacks where the adversary knows the plaintext for all the ciphertexts he submits, then the attacker learns nothing new when the original scheme is used, but learns the discrete log of ḡ base \overline{(1 + n)} in case of the naive threshold variant.

So clearly, this simple scheme is not as secure as the original one, and we need to be more careful. The natural solution is to conduct the entire decryption algorithm in a multiparty fashion, such that the only piece of information that the servers release is the plaintext. However, the decryption algorithm consists, first of computation modulo n^{2}, then some integer arithmetic, and finally computation modulo n. Doing this in a distributed way seems to require the full power of general multiparty computation, and would certainly require heavy interaction between the servers, something we definitely want to avoid in a practical application. We therefore propose a way to change the decryption algorithm such that one exponentiation essentially produces the plaintext directly without releasing extra information.

When the keys are generated, we first choose n, g as before. For consistency with the following, let us assume that n = pq, where p = q = 3 mod 4. This means that λ = 2m where m is odd. Then we compute j such that ḡ = \overline{1 + n}^{j} using our knowledge of λ. Finally, we compute a number d such that d = 0 mod m and d = j^{−1} mod n. This is easy by the Chinese Remainder theorem, since n and m are relatively prime. Note also that since ḡ generates Ḡ, j must be prime to n. We can now see that raising to exponent 2d essentially produces the decryption directly. By choice of d and the fact that g can be written as g = (1 + n)^{j}h for some h ∈ H, we get:

\begin{aligned}E(i, r)^{2d} & = (1 + n)^{2jid}(h^{i}r^{n})^{2d} = (1 + n)^{2jidmodn} \\ & = (1 + n)^{2i} = 1 + 2in mod n^{2} \end{aligned}

and so L(E(i, r)^{d} mod n^{2})/2 = i mod n. The last computation of L() is trivial and easy to reverse, so now the result of the exponentiation does not reveal any extra information.

We now briefly explain how the method from [8] can be used in our context: In [8] a method for distributed RSA signatures is given. Compared to [8] we still have a secret exponent d, but there is no public exponent e, so we will have to do something slightly different at some places. We will assume that there are l decryption servers, and a minimum of k of these are needed to make a correct decryption.

Key generation Key generation starts out as in [8]: we find 2 primes p and q, that satisfies p = 2p′+1 and q = 2q′+1, where p′ and q′ are primes and different from p and q. We set n = pq and m = p′q′ and we make g = (1 + n)^{j}b^{n} mod n^{2} for a random b ∈ Z_{n}^{∗}). In accordance with the basic idea from before we pick d to satisfy d = 0 mod m and d = j^{−1} mod n. Now we make the polynomial f(X) = ∑_{i=0}^{k−1} a_{i}X^{i} mod nm, by picking a_{i} (for 0 < i < k) as random values from {0, ⋯, n ∗ m − 1} and a_{0} = d. The secret share of the i’th authority will be s_{i} = f(i) for 1 ≤ i ≤ l and the public key will be (g, n). For verification of the actions of the decryption servers, we need the following fixed public values: v, generating the cyclic group of squares in Z_{n^{2}}^{∗} and for each decryption server a verification key v_{i} = v^{Δs_{i}} mod n^{2}, where Δ = l!.

Encryption To encrypt a message M, a random r ∈ Z_{n}^{∗} is picked and the cipher text is computed as c = g^{M}r^{n} mod n^{2}.

Share Decryption The i’th authority will compute c_{i} = c^{2Δs_{i}}, where c is the ciphertext. Along with this will be a proof that log_{c^{4}}(c_{i}^{2}) = log_{v}(v_{i}), which will convince us, that he has indeed raised to his secret exponent s_{i} ^{2}

Share combining If we have the required k (or more) number of shares with a correct proof, we can combine them into the result by taking a subset S of k shares and combine them to

c′ = ∏_{i∈S} c_{i}^{2λ_{0,i}^{S}} mod n^{2} where λ_{0,i}^{S} = Δ ∏_{i′∈S\i} \frac{−i}{i − i′} ∈ Z

The value of c′ will have the form c′ = c^{4Δ^{2}f(0)} = c^{4Δ^{2}d}. Noting that 4Δ^{2}d = 0 mod λ and 4Δ^{2}d = 4Δ^{2}j^{−1} mod n, we can conclude that c′ = (1 + n)^{4Δ^{2}M} mod n^{2}, where M is the desired plaintext, so this means we can compute M = L(c′)/4Δ^{2} mod n.

Compared to the scheme proposed in [4], there are only minor differences: in [4], an extra random value related to the public element g is part of the public key and is used in the Share combining algorithm. This is avoided in our scheme by the way we choose d, and thus we get a slightly shorter public key and a slightly simpler decryption algorithm.

The system as described requires a trusted party to set up the keys. This may be acceptable as this is a once and for all operation, and the trusted party can delete all secret information as soon as the keys have been distributed. However, using multiparty computation techniques it is also possible to do the key generation without a trusted party. In the full version of this paper, we will include a proof in the random oracle model that this threshold version is as secure as Paillier’s original scheme.

3.2 Some Auxiliary Protocols

Suppose a prover P presents a sceptical verifier V with a ciphertext c and claims that it encodes plaintext i. A trivial way to convince

2 A noninteractive proof for this using the Fiat-Shamir heuristic is easy to derive from the corresponding one in [8], see also [4].

V would be to reveal also the random choice r, then V can verify himself that c = E(i, r). However, for use in the following, we need a solution where no extra useful information is revealed.

It is easy to see that that this is equivalent to convincing V that cg^{−i} mod n^{2} is an n’th power. So we now propose a protocol for this which is a simple generalisation of the one from [5]. We note that this and the following protocols are not zero-knowledge as they stand, only honest verifier zero-knowledge. However, first zero-knowledge protocols for the same problems can be constructed from them using standard methods and secondly, in our applications, we will always be using them in a non-interactive variant based on the Fiat-Shamir heuristic, which means that we cannot obtain zeroknowledge, we can, however, obtain security in the random oracle model. As for soundness, we prove that the protocols satisfy so called special soundness (see [1]), which in particular implies that they satisfy standard knowledge soundness.

Protocol for n’th powers Input: n, u Private Input for P: v, such that u = v^{n} mod n^{2}

1. P chooses r at random mod n^{2} and sends a = r^{n} mod n^{2} to V 2. V chooses e, a random k bit number, and sends e to P.

3. P sends z = rv^{e} mod n^{2} to V, and V checks that z^{n} = au^{e} mod n^{2}, and accepts if and only if this is the case.

It is now simple to show

Lemma 1. The above protocol is complete, honest verifier zero-know-ledge, and satisfies that from any pair of accepting conversations (between V and any prover) of form (a, e, z), (a, e′, z′) with e ≠ e′, one can efficiently compute an n’th root of u, provided 2^{t} is smaller than the smallest prime factor of n.

Proof. Completeness is obvious from inspection of the protocol. For honest verifier simulation, the simulator chooses a random z ∈ Z_{n^{2}}^{∗}, a random e, sets a = z^{n}u^{−e} mod n^{2} and outputs (a, e, z). This is easily seen to be a perfect simulation.

For the last claim, observe that since the conversations are accepting, we have z^{n} = au^{e} mod n^{2} and z′^{n} = au^{e′} mod n^{2}, so we get

(z/z′)^{n} = u^{e−e′} mod n^{2}

Since e − e′ is prime to n by the assumption on 2^{t}, choose α, β such that αn + β(e − e′) = 1. Then let v = u^{α}(z/z′)^{β} mod n^{2}. We then get

v^{n} = u^{αn}(z/z′)^{nβ} = u^{αn}u^{β(e−e′)} = u mod n^{2}

so that v is indeed the desired n’th root of u

In our application of this protocol, the modulus n will be chosen by a trusted party, or by a multiparty computation such that n has two prime factors of roughly the same size. Hence, if k is the bit length of n, we can set t = k/2 and be assured that a cheating prover can make the verifier accept with probability ≤ 2^{−t}.

The lemma immediately implies, using the techniques from [1], that we can build an efficient proof that an encryption contains one of two given values, without revealing which one it is: given the encryption C and the two candidate plaintexts i_{1}, i_{2}, prover and verifier compute u_{1} = C/g^{i_{1}} mod n^{2}, u_{2} = C/g^{i_{2}} mod n^{2}, and the prover shows that either u_{1} or u_{2} is an n’th power. This can be done using the following protocol, where we assume without loss of generality that the prover knows an n’th root u_{1}, and where M denotes the honest-verifier simulator for the n-power protocol above:

Protocol 1-out-of-2 n’th power Input: n, u_{1}, u_{2} Private Input for P: v_{1}, such that u_{1} = v_{1}^{n} mod n^{2}

1. P chooses r_{1} at random mod n^{2}. He invokes M on input n, u_{2} to get a conversation a_{2}, e_{2}, z_{2}. He sends a_{1} = r^{n} mod n^{2}, a_{2} to V

2. V chooses s, a random t bit number, and sends s to P.

3. P computes e_{1} = s − e_{2} mod 2^{k} and z_{1} = r_{1}v_{1}^{e_{1}} mod n^{2}. He then sends e_{1}, z_{1}, e_{2}, z_{2} to V.

4. V checks that s = e_{1} + e_{2} mod 2^{k}, z_{1}^{n} = a_{1}u_{1}^{e_{1}} mod n^{2} and z_{2}^{n} = a_{2}u_{2}^{e_{2}} mod n^{2}, and accepts if and only if this is the case.

The proof techniques from [1] and Lemma 1 immediately imply

Lemma 2. Protocol 1-out-of-2 n’th power is complete, honest verifier zero-knowledge, and satisfies that from any pair of accepting conversations (between V and any prover) of form (a_{1}, a_{2}, s, e_{1}, z_{1}, e_{2}, z_{2}), (a_{1}, a_{2}, s′, e′_{1}, z′_{1}, e′_{2}, z′_{2}) with s ≠ s′, one can efficiently compute an n’th root of u_{1}, an n’th root of u_{2}, provided 2^{t} is less than the smallest prime factor of n.

Our final building block allows a prover to convince a verifier that three encryptions contain values a, b and c such that ab = c mod n. For this, we propose a protocol inspired by a similar construction found in [2].

Protocol Multiplication-mod-n Input: n, g, e_{a}, e_{b}, e_{c} Private Input for P: a, b, c, r_{a}, r_{b}, r_{c} such that ab = c mod n and e_{a} = E(a, r_{a}), e_{b} = E(b, r_{b}), e_{c} = E(c, r_{c})

1. P chooses a random value d ∈ Z_{n} and sends to V encryptions e_{d} = E(d, r_{d}), e_{db} = E(db, r_{db}).

2. V chooses e, a random t-bit number, and sends it to P.

3. P opens the encryption e_{a}^{e}e_{d} = E(ea + d, r_{a}^{e}r_{d} mod n^{2}) by sending f = ea + d mod n and z_{1} = r_{a}^{e}r_{d} mod n^{2}. Finally, P opens the encryption e_{b}^{f}(e_{db}e_{c}^{e})^{−1} = E(0, r_{b}^{f}(r_{db}r_{c}^{e})^{−1} mod n^{2}) by sending z_{2} = r_{b}^{f}(r_{db}r_{c}^{e})^{−1} mod n^{2}.

4. V verifies that the openings of encryptions in the previous step were correct, and accepts if and only if this was the case.

Lemma 3. Protocol Multiplication-mod-n is complete, honest verifier zero-knowledge, and satisfies that from any pair of accepting conversations (between V and any prover) of form (e_{d}, e_{db}, e, f, z_{1}, z_{2}), (e_{d}, e_{db}, e′, f′, z′_{1}, z′_{2}) with e ≠ e′, one can efficiently compute the plaintext a, b, c corresponding to e_{a}, e_{b}, e_{c} such that ab = c mod n, provided 2^{t} is smaller than the smallest prime factor in n.

Proof. Completeness is clear by inspection of the protocol. For honest verifier zero-knowledge, observe that the equations checked by V are e_{a}^{e}e_{d} = E(f, z_{1}) mod n^{2} and e_{b}^{f}(e_{db}e_{c}^{e})^{−1} = E(0, z_{2}) mod n^{2}. ¿From this it is clear that we can generate a conversation by choosing first f, z_{1}, z_{2}, e at random, and then computing e_{d}, e_{db} that will satisfy the equations. This only requires inversion modulo n^{2}, and generates the right distribution because the values f, z_{1}, z_{2}, e are also independent and random in the real conversation. For the last claim, note first that since encryptions uniquely determine plaintexts, there are fixed values a, b, c, d contained in e_{a}, e_{b}, e_{c}, e_{d}, and a value x contained in e_{db}. The fact that the conversations given are accepting implies that f = ea + d mod n, f′ = e′a + d mod n, fb − x − ec = 0 = f′b − x − e′c mod n. Putting this together, we obtain (f − f′)b = (e − e)′c mod n or (e − e′)ab = (e − e′)c mod n. Now, since (e − e′) is invertible modulo n by assumption on 2^{t}, we can conclude that c = ab mod n (and also compute a, b and c).

The protocols from this section can be made non-interactive using the standard Fiat-Shamir heuristic of computing the challenge from the first message using a hash function. This can be proved secure in the random oracle model.

4 Efficient Electronic Voting

In [3], a general model for elections was used, which we briefly recall here: we have a set of voters V_{1}, ..., V_{M}, a bulletin board B, and a set of tallying authorities A_{1}, ..., A_{v}. The bulletin board is assumed to function as follows: every player can write to B, and a message cannot be deleted once it is written. All players can access all messages written, and can identify which player each message comes from. This ca n all be implemented in a secure way using an already existing public key infrastructure and server replication to prevent denial of service attacks. We assume that the purpose of the vote is to elect a winner among L candidates, and that each voter is allowed to vote for t < L candidates.

In the following, h will denote a fixed hash function used to make non-interactive proofs according to the Fiat-Shamir heuristic. Alos, we will assume throughout that an instance of threshold version of Paillier’s scheme with public key n, g has been set up, with the A_{i}’s acting as decryption servers. We will assume that n > M, which will always be true for realistic values of these parameters.

The notation P roof_{P} (S), where S is some logical statement will denote a bit string created by player P as follows: P selects the appropriate protocol from the previous section that can be used to interactively prove S. He computes the first message a in this protocol, computes h(a, ID(P)) where ID(P) is his user identity in the system and, taking the result of this as the challenge from the verifier, computes the answer z. Then P roof_{P} (S) = (a, z). The inclusion of ID(P) in the input to h is done in order to prevent vote duplication.

A protocol for the case L = 2 is now simple to describe. This is equivalent to a yes/no vote and so each vote can thought of as a number equal to 0 for no and 1 for yes:

1. Each voter V_{i} decides on his vote v_{i}, he calculates E_{i} = E(v_{i}, r_{i}), where r_{i} is randomly chosen. He also creates P roof_{V_{i}}(E_{i} or E_{i}/g is an n’th power modulo n^{2}) based on the 1-out-of-2 n’th power protocol. He writes the encrypted vote and proof to B.

2. Each A_{j} does the following: first set E = 1. Then for all i: check the proof written by V_{i} on B and if is it valid, then E := E · E_{i} mod n^{2}. Finally, A_{j} executes his part of the threshold decryption protocol, using E as the input ciphertext, and writes his result to B.

3. ¿From the messages written by the A_{j}’s, anyone can now reconstruct the plaintext corresponding to E (possibly after discarding invalid messages). Assuming for simplicity that all votes are valid, it is evident that E = ∏_{i} E(v_{i}, r_{i}) = E(∑_{i} v_{i} mod n, ∏_{i} r_{i} mod n^{2}). So the decryption result is ∑_{i} v_{i} mod n which is ∑_{i} v_{i} since n > M.

Security of this protocol (in the random oracle model) follows easily from security of the sub-protocols used, and semantic security of Paillier’s encryption scheme. Proofs will be included in the final version of this paper.

There are several ways to generalise this to L > 2. Probably the simplest way is to hold L parallel yes/no votes as above. A voter votes 1 for the candidates he wants, and 0 for the others. This means that V_{i} will send L votes of form (j = 1, .., L)

E_{ij} =E(v_{ij}, r_{ij}),
P roof_{V_{i}}(E_{ij} or E_{ij}/g is an n’th power modulo n^{2})

To prove that he voted for exactly t candidates, he also writes to B the number ∏_{j} r_{ij} mod n^{2}. This allows the talliers to verify that ∏_{j} E(v_{ij}, r_{ij}) is an encryption of t. This check is sufficient, since all individual votes are proved to be 0 or 1. It is immediate that decryption of the L results will immediately give the number of votes each candidate received.

We note that his easily generalises to cases where voters are allowed to vote for up to t candidates: one simply introduces t ”dummy candidates” in addition to the actual L. We then execute the protocol as before, but with t + L candidates. Each voter places the votes he does not want to use on dummy candidates.

The size of a vote in this protocol is seen to be O(Lk), where k is the bit length of n, by simple inspection of the protocol. The protocol requires L decryption operations. As a numeric example, suppose we have k = 1000, M = 64000, L = 64. Then a vote in the above system has size about 80 Kbyte.

If the parameters are such that L log_{2} M < k and t = 1, then we can do significantly better. These conditions will be satisfied in many realistic situations, such as for instance in the numeric example above. Note that for security reasons, one would want k ≥ 1000 in any case, so the variant we propose here can indeed handle realistic values of M, L without having to increase k.

The basic idea is the following: a vote for candidate j, where 0 ≤ j < L is defined to be an encryption of the number M^{j}. Each voter will create such an encryption and prove its correctness as detailed below. When all these encryptions are multiplied we get an encryption of a number of form a = ∑_{j=0}^{L} a_{j}M^{j} mod n, where a_{j} is the number of votes cast for candidate j. Since L log_{2} M < k, this relation also holds over the integers, so decrypting and writing a in M-ary notation will directly produce all the a_{j}’s.

It remains to describe how to produce encryption hiding a number of form M^{j}, for some 0 ≥ j < L, and prove it was correctly formed. Let b_{0}, ..., b_{l} be the bits in the binary representation of j, i.e. j = b_{0}2^{0} + b_{1}2^{1} + ... + b_{l}2^{l}. Then clearly we have M^{j} = (M^{2^{0}})^{b_{0}} · ... · (M^{2^{l}})^{b_{l}}. Each factor in this product is either 1 or a power of M. This is used in the following algorithm for producing the desired proof (where P denotes the prover):

1. P computes encryptions e_{0}, ..., e_{l} of (M^{2^{0}})^{b_{0}}, ..., (M^{2^{l}})^{b_{l}}. For each i = 0...l he also computes P roof_{P} (e_{i}/g or e_{i}/g^{M^{i}} is an n’th power).

2. Let F_{i} = (M^{2^{0}})^{b_{0}} · ... · (M^{2^{i}})^{b_{i}}, for i = 0...l. P computes an encryption f_{i} of F_{i}, for i = 1..l. We set f_{0} = e_{0}. Now, for i = 1...l, P computes

P roof_{P} (Plaintexts corr. to f_{i−1}, e_{i}, f_{i} satisfy
F_{i−1} · (M^{2^{i}})^{b_{i}} = F_{i} mod n ),

based on the multiplication-mod-n protocol. The encryption f_{l} is the desired encryption, it can be verified from the e_{i}, f_{i} and all the proofs computed.

It is straightforward to see that a vote in this system will have length O(k log L) bits (still assuming, of course, that k log_{2} M ≤ k).

With parameter values as in the numeric example before, a vote will have size about 15 Kbyte, a factor of more than 5 better than the previous system. Moreover, we need only 1 decryption operation as opposed to L before.

5 Reducing the Expansion Factor

Paillier’s original system expands a plaintext to a ciphertext that is twice as long. We now show how this expansion factor can be made smaller. The basic idea is simple: to make keys, choose an RSA modulus n as usual, but do the computations modulo n^{s+1}, for some s > 1.

It is easy to see that the group Z_{n^{s+1}}^{∗} is isomorphic to the direct product of a cyclic group of order n^{s} and a group H of order ϕ(n). Again we will consider the factor group coming from factoring out H, which this time has order n^{s}. Carrying over ideas from the previous sections, we have the following lemma:

Lemma 4. For any s < p, q, the element n + 1 has order n^{s} in Z_{n^{s+1}}^{∗}.

Proof. Consider the integer (1 + n)^{i} = ∑_{j=0}^{i} \binom{i}{j}n^{j}. This number is 1 modulo n^{s+1} for some i if and only if ∑_{j=1}^{i} \binom{i}{j}n^{j−1} is 0 modulo n^{s}. Clearly, this is the case if i = n^{s}, so it follows that the order of 1 + n is a divisor in n^{s}, i.e., it is a number of form p^{α}q^{β}, where α, β ≤ s. Set a = p^{α}q^{β}, and consider a term \binom{a}{j}n^{j−1} in the sum ∑_{j=1}^{a} \binom{a}{j}n^{j−1}.

We claim that each such term is divisible by a: this is trivial if j > s, and for j ≤ s, it follows because j! can then not have p or q as prime factors, and so a must divide \binom{a}{j}. Now assume for contradiction that a = p^{α}q^{β} < n^{s}. Without loss of generality, we can assume that this means α < s. We know that n^{s} divides ∑_{j=1}^{a} \binom{a}{j}n^{j−1}. Dividing both numbers by a, we see that p must divide the number ∑_{j=1}^{a} \binom{a}{j}n^{j−1}/a. However, the first term in this sum after division by a is 1, and all the rest are divisible by p, so the number is in fact 1 modulo p, and we have a contradiction.

As previously, this means that we can number the residue classes of H in a natural way, and that for an element a in the i’th residue class, we have that a = (1 + n)^{i}h for an element h ∈ H, and so

a^{λ} = (1 + n)^{iλmodn^{s}} mod n^{s+1}

Just as before, this means that if we can compute i from (1 + n)^{i} mod n^{s+1} efficiently, then knowledge of λ will enable us to compute discrete logs efficiently in the factor group, and we can devise a decryption algorithm along the lines of the system using n^{2} as modulus. Clearly, we have

L((1 + n)^{i} mod n^{s+1}) = (i + \binom{i}{2}n + ... + \binom{i}{s}n^{s−1}) mod n^{s}

We now describe an algorithm for computing i from this number.

The general idea of the algorithm is to extract the value part by part, so that we first extract i_{1} = i mod n, then i_{2} = i mod n^{2} and so forth. To see how this can be done let’s look at the j’th step where we know i_{j−1}. This means that i_{j} = i_{j−1} + k ∗ n^{j−1} for some 0 ≤ k < n. If we use this in

L((1 + n)^{i} mod n^{j+1}) = (i_{j} + \binom{i_{j}}{2}n + ... + \binom{i_{j}}{j}n^{j−1}) mod n^{j}

We can notice that each term \binom{i_{j}}{t+1}n^{t} for j > t > 0 satisfies that \binom{i_{j}}{t+1}n^{t} = \binom{i_{j−1}}{t+1}n^{t} mod n^{j}. This is because the contributions from k ∗n^{j−1} vanish modulo n^{j} after multiplication by n. This means that we get:

\begin{matrix}L((1 + n)^{i} mod n^{j+1}) = ( & i_{j−1} + k ∗ n^{j−1} + \binom{i_{j−1}}{2}n + ... + \\ \binom{i_{j−1}}{j}n^{j−1}) mod n^{j} \end{matrix}

Then we just rewrite that to get what we wanted

i_{j} = i_{j−1} + k ∗ n^{j−1}

= i_{j−1} + L((1 + n)^{i} mod n^{j+1}) − (i_{j−1} + \binom{i_{j−1}}{2}n

+ ... + \binom{i_{j−1}}{j}n^{j−1}) mod n^{j}

= L((1 + n)^{i} mod n^{j+1}) − (\binom{i_{j−1}}{2}n + ... + \binom{i_{j−1}}{j}n^{j−1}) mod n^{j}

This equation leads to the following algorithm:

i := 0;

\underline{for} j:= 1 \underline{to} s \underline{do}

\underline{begin} t_{1} := L(a mod n^{j+1}); t_{2} := i; \underline{for} k:= 2 \underline{to} j \underline{do} \underline{begin}

i := i − 1;

t_{2} := t_{2} ∗ i mod n^{j};

t_{1} := t_{1} − \frac{t_{2}∗n^{k−1}}{k!} mod n^{j}; \underline{end} i := t_{1};

\underline{end}

As in Paillier’s original system, we will use as public key in our system pairs n, g, where n is an RSA modulus and g is a random element of order n^{s} in the factor group Z_{n^{s+1}}^{∗}/H. The secret key is λ. An encryption of i ∈ Z_{n^{s}} is of form E_{s}(i, r) = g^{i}r^{n} mod n^{s+1}, where r is randomly chosen in Z_{n^{s+1}}^{∗}. By the algorithm above, knowledge of the secret λ enables us to compute discrete logarithms in the factor group, and a decryption algorithm follows easily.

If n is a k-bit number, then this system encrypts a ks bit message to a k(s + 1) bit ciphertext, and so the expansion factor can be brought arbitrarily close to 1, by choosing s larger.

It is worth noting that all the auxiliary protocols we developed earlier extend trivially to the case of computations modulo n^{s+1}, in particular the scheme is homomorphic w.r.t. addition of messages modulo n^{s}. Consequently our voting schemes can all be implemented based on this variant, which in particular gives the possibility in the most efficient scheme to accomodate a larger number of voters without increasing the size of the modulus.

The system is semantically secure, if the following assumption holds

Conjecture 1. Let A be any probabilistic polynomial time algorithm, and assume A gets n, g as input (n has k bits, n, g chosen as described above), it outputs i_{0}, i_{1} ∈ Z_{n^{s}}, it gets E_{s}(i_{b}, r), where b is randomly chosen, and finally outputs a bit c. Let p(A, k) be the probability that c = b. Then | 1/2 − p(A, k) | is negligible in k.

By reducing everything modulo n^{2}, it is easily seen that this conjecture implies Paillier’s original intractability assumption. It is not clear if the reverse implication is true, in particular, if i_{0}, i_{1} are different modulo n^{s} but the same modulo n^{2}, then encryptions modulo n^{s+1} of i_{0}, i_{1} might be easy to distinguish even if Paillier’s original system is secure. We recommend that these systems are used with caution, until this family of intractability assumptions has been studied more carefully.

References

1. Cramer, Damgaård and Schoenmakers: Proofs of partial knowlegde, Proc. of Crypto 94, Springer Verlag LNCS series nr. 839.

2. R.Cramer, S.Dziembowski, I. Damgård, M.Hirt and T.Rabin: Efficient Multiparty Computations Secure against an Adaptive Adversary, Proc. of EuroCrypt 99, Springer Verlag LNCS series 1592, pp. 311-326.

3. R.Cramer, R.Gennaro, B.Schoenmakers: A Secure and Optimally Efficient Multi-Authority Election Scheme, Proceedings of EuroCrypt 97, Springer Verlag LNCS series, pp. 103-118.

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

5. L. Guillou and J.-J. Quisquater: A Practical Zero-Knowledge Protocol fitted to Security Microprocessor Minimizing both Transmission and Memory, Proc. of EuroCrypt 88, Springer Verlag LNCS series.

6. M.Hirt and K.Sako: Efficient Receipt-Free Voting based on Homomorphic Encryption, to appear in Proc. of EuroCrypt 2000.

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

8. V.Shoup: Practical Threshold Signatures, to appear in Proceedings of EuroCrypt 2000.

Recent BRICS Report Series Publications

RS-00-5 Ivan B. Damgård and Mads J. Jurik. Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes. March 2000. 19 pp.

RS-00-4 Rasmus Pagh. A New Trade-off for Deterministic Dictionaries. February 2000.

RS-00-3 Fredrik Larsson, Paul Pettersson, and Wang Yi. On Memory-Block Traversal Problems in Model Checking Timed Systems. January 2000. 15 pp. To appear in Tools and Algorithms for The Construction and Analysis of Systems: 6th International Conference, TACAS ’00 Proceedings, LNCS, 2000.

RS-00-2 Igor Walukiewicz. Local Logics for Traces. January 2000. 30 pp.

RS-00-1 Rune B. Lyngsø and Christian N. S. Pedersen. Pseudoknots in RNA Secondary Structures. January 2000. 15 pp. To appear in Fourth Annual International Conference on Computational Molecular Biology, RECOMB ’00 Proceedings, 2000.

RS-99-57 Peter D. Mosses. A Modular SOS for ML Concurrency Primitives. December 1999. 22 pp.

RS-99-56 Peter D. Mosses. A Modular SOS for Action Notation. December 1999. 39 pp. Full version of paper appearing in Mosses and Watt, editors, Second International Workshop on Action Semantics, AS ’99 Proceedings, BRICS Notes Series NS-99-3, 1999, pages 131–142.

RS-99-55 Peter D. Mosses. Logical Specification of Operational Semantics. December 1999. 18 pp. Invited paper. Appears in Flum, Rodríguez-Artalejo and Mario, editors, European Association for Computer Science Logic: 13th International Workshop, CSL ’99 Proceedings, LNCS 1683, 1999, pages 32–49.

RS-99-54 Peter D. Mosses. Foundations of Modular SOS. December 1999. 17 pp. Full version of paper appearing in Kuty�owski, Pacholski and Wierzbicki, editors, Mathematical Foundations of Computer Science: 24th International Symposium, MFCS ’99 Proceedings, LNCS 1672, 1999, pages 70–80.