The Paillier Cryptosystem with Applications to Threshold ECDSA
You may have heard of RSA (b. 1977), but have you heard of its cousin, Paillier (b. 1999)? In this post, we provide a close look at the Paillier homomorphic encryption scheme [Paillier1999], what it offers, how it’s used in complex protocols, and how to implement it securely.
Contents
RSA Encryption Refresher and Notation
The Computational Composite Residuosity Class Problem
Security and Homomorphic Properties
Applications and Protocols using Paillier Encryption
[Lindell2017], [GenGol2019], [CanGenGolMakPel2021]
Key generation, Encryption, Decryption, Homomorphic operations
RSA Encryption Refresher and Notation
We’ll start with a review of RSA encryption and two related functions: Euler’s phi function and Carmichael’s lambda function .
RSA works in a group where is a product of two distinct primes (also called a biprime or an RSA prime). Both plaintexts and ciphertexts are in this group.
For any integer , is the set of integers less than and co-prime to and it always forms a multiplicative group called the group of units modulo . An integer less than and co-prime to is called a totative of .
The primes and should be chosen independently and randomly. RSA moduli don’t need to be generated with safe primes or strong primes; two random primes are fine. (In 1999, Rivest and Silverman published an article titled “Are ‘Strong Primes’ Needed for RSA?” (PDF) in which they argued that it is unnecessary to use strong primes.)
The number of elements in is, by definition, .
For any integer , is Euler’s phi (or totient) function, defined as the number of totatives of (i.e., positive integers less than or equal to that are co-prime to it). Euler’s phi function is a multiplicative function: if and are co-prime, then .
In the RSA setting, is a product of two distinct primes, so the size of is .
The RSA cryptosystem uses a public encryption exponent and a private decryption exponent . Encrypting a message is done by computing , and decrypting a ciphertext is done by computing . For these operations to be correct, they must be inverses of each other: it’s required that for all . In other words, and must satisfy for every possible message .
The order of an integer modulo is the smallest positive integer such that (or undefined if no such exists, but this case won’t arise in this blog post).
For RSA decryption and encryption to be correct for all possible messages , it is necessary and sufficient for the product to be congruent to 1 modulo .
For any integer , is Carmichael’s lambda (or least universal exponent) function, defined as the smallest positive integer such that for all totatives . It is the least common multiple of the orders of all elements in , so it is always less than or equal to the order of the group, . If (and only if) , then the group has a generator. (See the first definition of the Carmichael function at Wolfram MathWorld.)
Unlike Euler’s phi function, Carmichael’s lambda function is not quite a multiplicative function, but it satisfies a similar property: if and are co-prime, then , where is the least common multiple function. It turns out that if is a power of an odd prime, say , then . (The value of for is slightly different: it is either for , or for , but this fact won’t be used in this post.)
Just as can be efficiently computed when ’s factorization into prime powers is known, can also be efficiently computed based on ’s factorization into prime powers.
You may have learned RSA encryption with the requirement that modulo instead of modulo — this is how I learned it too. Although this condition with Euler’s phi function is sufficient for correctness (since always divides ), it is not necessary (since is always at most ).
In this post, only two values of the Carmichael lambda function will arise: and , for with odd primes and . Their values are and .
The Computational Composite Residuosity Class Problem
RSA encryption is effective at hiding data because it’s believed to be hard to find th roots modulo a product of two primes, . This is (rather redundantly) called the RSA problem.
Let be a biprime and let be an integer greater than 2 in . The RSA problem is to solve the equation for given a random .
For Paillier encryption, we again consider some integer that is a product of two primes, with the additional requirement that . An easy way to guarantee this requirement is satisfied is to choose and to have the same bitlength (i.e., to have their most significant bit in the same position). Instead of working with ciphertexts that are integers modulo as in RSA, Paillier ciphertexts are integers modulo . Specifically, Paillier ciphertexts are in , the group of units modulo , which has order for a biprime .
There are multiple ways to think of the set of integers in this group. Here’s a non-obvious one: for an appropriate choice of base (having a particular property, as we will explain soon), each integer in corresponds to a pair of integers , where is in , is in the group of units , and .
While it’s easy to compute given a pair for a fixed base modulo , it’s believed to be hard to compute the unique, corresponding pair for a particular without some additional information.
Not every possible value of is an appropriate base; must be chosen so that for every in , there is exactly one pair in such that . It turns out (see Lemma 3 of [Paillier1999]) that we get this property exactly when is an element of whose order is a (non-zero) multiple of . Since the order of any element in is at most , bases are those elements with orders in . (There isn’t necessarily a base with each of these orders; the order of any element in must divide .)
In other words, is an appropriate base when there’s a (non-zero) multiple of such that , but for any positive integer .
For some biprime , is called a base if its order modulo is a non-zero multiple of .
With such a base, the correspondence between a and some is a proper bijection. Although this post won’t prove that the mapping yields a bijection, you can do a quick, reassuring check that both groups have the same size, . (For the full proof, see Lemma 3 of [Paillier1999]). The first element of the pair, , is called the th residuosity class of with respect to and Paillier is effective at hiding data because computing it is believed to be a hard problem.
Let be a biprime and let be a base. Given , , and a random value , the composite residuosity class problem is to compute the unique such that for some .
There are many potential bases having orders modulo that are non-zero multiple of . However, there’s no need to run a complex algorithm to identify one due to a nice property of the set of potential bases: the hardness of computing the residuosity class of a random modulo relative to some base doesn’t actually depend on the choice of ! (For the proof, see Lemma 7 of [Paillier1999].) A common choice of base is , which has order , because it allows optimizations during encryption and decryption.
The Paillier Cryptosystem
The Paillier cryptosystem is built so that decrypting a ciphertext corresponds to solving the computational composite residuosity class problem. First, we’ll go over the mechanics of key generation, encryption, and decryption, and then we’ll dive in to how decryption works and explain the trick that allows doing it efficiently.
Key generation. Pick two primes and of the same bitlength independently at random. Let be their product. Choose a base whose order is a non-zero multiple of , e.g., . Compute the Carmichael lambda function of : . The public key is and the private key is .
Encryption of a message . Pick a random integer and compute the ciphertext .
Decryption of a ciphertext . Compute the two values and . Then, compute the resulting message .
One of the brilliant properties of Paillier’s scheme is that knowing the factorization of allows efficiently computing composite residuosity classes: calculating gives a trapdoor for computing the necessary discrete logarithm.
Recall that, for a base , any can be written as for a unique pair of and — these and values just aren’t known yet. Decryption has three implicit sub-steps: cancelling out the random value , bringing the plaintext down from the exponent, and isolating from values that depend on the base .
Cancelling out the random value is straightforward when is a biprime.
Since the least universal exponent modulo is , raising to the power of modulo yields for some not-yet-known , because .
Next, we observe that the exponentiation in step 1 was enough to bring down from the exponent.
Raising any element to the power of modulo yields something called an th root of unity modulo . This is an element that, when raised to the power of , yields 1 — in other words, its order must be either or . This follows from the definition of the least universal exponent, . These th roots of unity modulo all have a particular form: they can be written as for some . To partially convince yourself this is true, observe that applying binomial expansion to modulo gives 1. (See Section 2 in [Paillier1999].) So, is an th root of unity and can be written as for some . The result of step 1 () can therefore be written as for some . By applying binomial expansion once more, we see that it can be written as . By subtracting 1 and dividing by (over the integers), we get the value of the dividend in the description of decryption above: .
Finally, we need to isolate by dividing by (modulo ).
The value of depends only on the base : , so . This is the value of in the description of decryption. The last step of decryption is to compute .
Security and Homomorphic Properties
Paillier encryption effectively hides data (the messages ) assuming that computing the th residuosity classes of ciphertexts is hard. More strongly, and more formally, Paillier ciphertexts are indistinguishable under chosen plaintext attacks (IND-CPA) assuming that deciding whether the th residuosity class of a ciphertext equals some given value is hard. (See Theorem 15 in [Paillier1999].)
However, Paillier ciphertexts cannot be indistinguishable under chosen ciphertext attacks (IND-CCA) because of the scheme’s homomorphic properties. In general, a homomorphic encryption scheme is one that allows certain operations to be performed on ciphertexts such that the resulting ciphertexts contain the encrypted result. Paillier encryption is additively homomorphic:
and
The first equation above says that multiplication of ciphertexts modulo corresponds to addition of plaintexts modulo . The second equation says that exponentiation of a ciphertext to a constant modulo corresponds to multiplication of a plaintext by a constant modulo .
In the context of IND-CCA security, these properties would allow an attacker with access to a decryption oracle (that works on any ciphertext besides the target ciphertext) to decrypt a target ciphertext by transforming it homomorphically before querying the oracle, and undoing the transformation after. In that sense, Paillier is no different than any other homomorphic encryption scheme: no homomorphic encryption scheme can offer IND-CCA security.
Applications and Protocols using Paillier Encryption
In the 20+ years since Pascal Paillier devised this encryption scheme, it has been used in a variety of cryptographic protocols and applications. One recent popular application is multi-party ECDSA signing protocols.
ECDSA produces signatures in a group of elliptic curve points over a field of order with generator of order . (We write and here to distinguish these primes from the factors of an RSA or Paillier modulus — they are completely different.) ECDSA private keys are elements (scalars) and public keys are the corresponding elliptic curve points, . The signature on a message whose hash is is computed as
where for a fresh, uniformly random .
In multi-party ECDSA signing protocols, two or more parties have shares of a private key and jointly generate signatures. These schemes typically provide security and correctness even when some small number of protocol participants misbehave. To achieve this, the use of Paillier encryption is often augmented with zero-knowledge proofs: for example, protocol participants can prove that their Paillier public keys were correctly generated, that ciphertexts encrypt values within given ranges, or that ciphertexts encrypt values corresponding to the discrete logarithm of some known public value.
Combining Paillier encryption — which works in groups modulo or , where is usually at least 2048 bits long — and ECDSA — which works in groups whose sizes are usually 256 bits — is not trivial. To illustrate this, we’ll examine three recent multi-party ECDSA protocols.
Lindell’s Two-Party ECDSA Protocol (2017)
Lindell’s two-party ECDSA signing protocol [Lindell2017] uses Paillier encryption to compute the component of the signature homomorphically. During key generation, the first party sends a Paillier encryption of their share of the ECDSA private key to the second party, along with zero-knowledge proofs that (i) their Paillier modulus satisfies , and (ii) the ciphertext is indeed an encryption of the discrete log of . Then, when generating a signature, the second party can craft most of the component of the signature by operating homomorphically on the encryption of and combining it with a ciphertext that it crafts. The second party sends back the Paillier ciphertext to the first party, who decrypts it and performs a final operation with their share of the nonce.
Since the second party crafted the ciphertext homomorphically, it cannot reduce the encrypted value modulo before sending it back to the first party, which may allow some information to leak. To prevent this, the second party must add a random multiple of when it is forming the ciphertext.
The proof that is described in a paper by Hazay, Mikkelsen, Rabin, Toft, and Nicolosi (eprint 2011/494, Section 3.3). Interestingly, proving that the Paillier modulus satisfies — which guarantees nothing about how many prime factors it has — is sufficient for the security of this particular ECDSA protocol: using the base , there is still the same isomorphism between and . The Paillier modulus must be at least , where is the size of the ECDSA group.
The Gennaro–Goldfeder Multi-Party Threshold ECDSA Protocol (2018–2021)
In Gennaro and Goldfeder’s threshold ECDSA protocol [GenGol2019], each party has their own Paillier key pair. Each Paillier modulus is accompanied by a zero-knowledge proof that it is square-free and that for any two prime factors and of the modulus, does not divide . This proof was devised by Gennaro, Micciancio, and Rabin (CCS 1998, PDF, Section 3.1). The protocol also requires that each Paillier modulus is greater than , where is the size of the ECDSA group.
Each participant has an additive share of the private ECDSA key . When the signing protocol is run, each party also randomly generates an additive share of the nonce inverse and an additive share of the nonce “mask” used to hide the value of (which, if leaked, would allow recovering the ECDSA private key). As part of jointly computing the signature, parties must compute additive shares of the products and . Paillier encryption is used in a sub-protocol for multiplicative-to-additive share conversion during the computation of additive shares of these two products.
Suppose there are parties whose goal is to jointly compute the product , and each party has additive shares and of and . The product can be written as
The share conversion protocol transforms multiplicative shares of values (the cross-terms ) held by parties and to equivalent additive shares ( and ) satisfying . It works as follows. First, party sends party a Paillier encryption of their multiplicative share (along with a zero-knowledge proof that the encrypted value is in the correct range respective to ). Party operates homomorphically on the ciphertext it received to compute an encryption of for a random (and provides a zero-knowledge proof that the ciphertext was formed with values from the correct ranges). Party then computes their additive share by decrypting this ciphertext and reducing it modulo . Party ’s additive share is .
Note that is sampled uniformly at random from , not (where is the ECDSA group size) or (where is the Paillier modulus). This modulus was chosen so that the range of possible values is big enough that the distribution of does not leak information about , but small enough that no reduction modulo the Paillier modulus occurs when homomorphically computing the ciphertext of .
Finally, after repeating this sub-protocol for all cross-terms in the product of , each party can compute their additive share of the product as . This is how additive shares of the products and are computed.
The Canetti–Gennaro–Goldfeder–Makriyannis–Peled Threshold ECDSA Protocol (2020–2021)
In Canetti, Gennaro, Goldfeder, Makriyannis, and Peled’s threshold ECDSA scheme [CanGenGolMakPel2021], each party has their own Paillier key pair that is accompanied by a proof that the modulus is a Paillier-Blum modulus (that it is a product of two primes congruent to 3 modulo 4 and that it satisfies ) and that it has no small factors.
Paillier encryption has several uses in this scheme.
First, it is used in a multiplicative-to-additive share conversion protocol like the ones in Gennaro and Goldfeder’s 2018 protocol, described earlier, to compute additive shares of and during signing. The zero-knowledge proof accompanying the first party’s (party ’s) message is like the one described earlier: it proves that the encrypted value is in the correct range with respect to . The proof accompanying party ’s message is slightly different than in Gennaro and Goldfeder’s multiplicative-to-additive share conversion scheme. Recall that party operates homomorphically on the ciphertext it received from party by multiplying it with and adding to it using party ’s Paillier key. Here, party provides a zero-knowledge proof that the ciphertext it sends back to party was formed with values from the correct ranges, and that (i) the multiplicative coefficient equals the discrete log of a certain known value, and (ii) the additive term equals the same value encrypted in a Paillier ciphertext using party ’s own key.
Paillier encryption is also used in a key refresh procedure, where each party chooses a random secret sharing of 0 (modulo the ECDSA group order ) and encrypts one share to each other party’s Paillier key. The parties then use the received shares to update their secret key shares without changing their shared public key.
Finally, the Paillier modulus is re-used as the modulus of ring Pedersen (Fujisaki–Okamoto) commitments (eprint 2001/064, PDF), whose security relies on the strong RSA problem. Each party has a pair of ring Pedersen parameters (where is their Paillier modulus), for which they provide a zero-knowledge proof that belongs to the multiplicative group generated by modulo . Ring Pedersen commitments are used in zero-knowledge proofs with the verifier’s Paillier modulus.
The paper includes the interesting observation that Paillier encryption can be used as a commitment scheme to simplify some zero-knowledge proofs. When a participant encrypts a plaintext with their own Paillier key, it produces a cryptographic commitment to that plaintext that is perfectly binding (due to the bijection between and ) and computationally hiding (due to Paillier’s IND-CPA security, assuming computing th residue classes is hard).
Interestingly, this paper defines Paillier decryption with instead of for the base . Since , the decryption equation is still correct with and .
Implementation Considerations
Key Generation
Paillier key generation has many of the same potential pitfalls as RSA key generation, as well as some other potential issues related to the choice of base.
First, the public key should be big enough that factoring it with modern, general-purpose algorithms, like the General Number Field Sieve (GNFS), is infeasible. For factoring the modulus with the GNFS to be roughly at least as hard as brute-forcing a 128-bit symmetric key, the modulus size should be at least 3072 bits, so the two prime factors and should be at least 1536 bits each.
It is crucial to use a good source of randomness when selecting primes and , and to choose them independently so that no special-purpose factoring algorithms apply. For example, if the primes are too close together, the modulus can be factored efficiently with Fermat’s factorization method.
The modulus must satisfy . An easy way to enforce this property is to choose the two primes and having exactly the same bitlength. If , then either divides or divides . And since , it will not be co-prime to either. This destroys the bijection between the groups and (for any base, even one with the correct order), and decryption no longer works. As a quick example, consider and , so is not co-prime with . First, raising an element to the power of , as is done to randomize ciphertexts during encryption, is a many-to-one function, which is enough to break the bijection. For example, Second, even with a proper base like , which has order modulo , decryption no longer works and many plaintexts can correspond to the same ciphertexts. For example, the five messages , , , , and would be indistinguishable during decryption after raising the ciphertext to the power of :
The order of the base modulo must be a non-zero multiple of .
Otherwise, there is no longer a bijection between the groups and . As a quick example, consider , , , and the base , which has order modulo (which is not a multiple of ). Then, encryption is a 13-to-1 mapping and every has 13 possible corresponding messages. For example, the ciphertext could be obtained by encrypting any one of :
Encryption
Paillier encryption is randomized and the random values must be carefully generated and handled.
It is important to use a good source of randomness when choosing , and to generate a fresh, independently chosen value of every time a message is encrypted. Known relations between the values of multiple ciphertexts can be exploited to learn information about their corresponding plaintexts. For example, suppose two ciphertexts and (encrypting and ) are known to have been generated with the base using random values that are inverses of each other modulo : and . Then, due to the additively homomorphic properties of Paillier ciphertexts and the cancellation of the random values, the sum of the plaintexts (modulo ) can be recovered by computing .
Since encryption includes modular exponentiation to a secret value (), a constant-time implementation — one without any data-dependent operations — must be used to avoid leaking information about the plaintext.
The random element also must be kept secret and handled in constant-time.
If the value corresponding to a particular ciphertext is ever leaked, the plaintext can be recovered by computing (e.g., using the Extended Euclidean Algorithm), then computing .
Decryption
Paillier decryption involves the secret key, , and the usual recommendations apply.
Since decryption includes modular exponentiation to the secret value , a constant-time implementation — one without any data-dependent operations — must be used to avoid leaking information about the key.
If the value of is pre-computed, it must be afforded the same protections as the secret key, .
Homomorphic Operations
Paillier homomorphic operations are a feature, not a bug! Still, some care must be taken.
It is important to remember that ciphertexts are malleable by design, and provide no message authentication — they can easily be tampered with.
Homomorphic operations apply modulo : when homomorphically adding two plaintexts or homomorphically multiplying a plaintext by some constant , the result will be their sum or product modulo .
Certain edge cases of homomorphic operations require explicit re-randomization to retain ciphertext indistinguishability.
To homomorphically multiply a ciphertext by 0 or 1, the ciphertext is raised to the power of 0 or 1 respectively, which either results in 1 or no change at all to the ciphertext. In these two cases, the ciphertext should be re-randomized by choosing a fresh random value and multiplying the ciphertext by modulo .
Conclusion
The Paillier cryptosystem is based on a fascinating number theoretic problem. Its homomorphic properties make it especially useful in multi-party computation protocols, such as many recent threshold ECDSA protocols. Since the security of Paillier is related to factoring, Paillier moduli must always be large enough that factoring them is infeasible. Protocols involving Paillier encryption and groups of different sizes must carefully account for the different sizes.
Finally, if being familiar with RSA and Paillier has made you want to learn more, consider reading about the Damgård–Jurik cryptosystem (b. 2001) in “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System” (PKC 2001, PDF).
References
[Paillier1999]: “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes” by Pascal Paillier, EUROCRYPT ’99. Available at https://link.springer.com/chapter/10.1007/3-540-48910-X_16.
[Lindell2017]: “Fast Secure Two-Party ECDSA Signing” by Yehuda Lindell, CRYPTO 2017. Available at https://link.springer.com/chapter/10.1007/978-3-319-63715-0_21 and https://eprint.iacr.org/2017/552.
[GenGol2019]: “Fast Multiparty Threshold ECDSA with Fast Trustless Setup” by Rosario Gennaro and Steven Goldfeder. Available at https://eprint.iacr.org/2019/114.
[CanGenGolMakPel2021]: “UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts” by Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. Available at https://eprint.iacr.org/2021/060.
Acknowledgements
Thank you to Paul Bottinelli, Giacomo Pope, and Eric Schorn of Cryptography Services and Paul Grubbs for comments on an earlier version of this blog post.
About The Author
