# How to apply two consecutive Paillier encryptions?

The plaintext space for Paillier encryption is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. How can I apply two consecutive encryptions?

I mean, if $c$ is the ciphertext of $m$, how to encrypt $c$?

• Does the second encryption have to use the same public key as the first? – mikeazo Mar 14 '18 at 17:00
• Not necessarily. – user48832 Mar 15 '18 at 10:43
• If they don't have to be the same, just make a really large second key. – mikeazo Mar 15 '18 at 10:52

• The ciphertext $c\in\mathbb{Z}_{n^2}$ is $2\log_2(n)$-bit long, so you can simply interpret it as a pair $(c_0,c_1)$ of $\log_2(n)$-bit string, that can in turn be seen as elements of $\mathbb{Z}_n$. Then, you can encrypt each component $(c_0,c_1)$ using Paillier again.
• There is a natural generalization of Paillier to longer plaintexts, the Damgård–Jurik cryptosystem. It allows to encrypt plaintexts from $\mathbb{Z}_{n^s}$, with a ciphertext in $\mathbb{Z}_{n^{s+1}}$, for any $s$ (Paillier is just the case $s=1$). Hence, you can directly encrypt $c\in\mathbb{Z}_{n^2}$ with the Damgård–Jurik scheme for $s=2$, and get a ciphertext in $\mathbb{Z}_{n^{3}}$. This approach gives a result more compact than the previous one ($3\log_2(n)$ bits in total, as opposed to $4\log_2(n)$ bits with the previous approach).