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$?

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

1 Answer 1


I do not know what would be the purpose of doing so, but there are two simple solutions:

  • 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.