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 '18 at 17:00
  • $\begingroup$ Not necessarily. $\endgroup$ – tamhzeo Mar 15 '18 at 10:43
  • $\begingroup$ If they don't have to be the same, just make a really large second key. $\endgroup$ – mikeazo Mar 15 '18 at 10:52

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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.