# Paillier Encryption: problems with double encryption

Given have two public keys $k1$ and $k2$, $E_{k1}(E_{k2}(m_1))$ and $m_2$.

Is it possible to calculate $E_{k1}(E_{k2}(m_1 + m2))$? (or with multiplication instead of addition)

At a first glance, I thought that it is possible:

1. Calculate $E_{k2}(m_2)$.
2. Calculate $E_{k1}(E_{k2}(m_1))^{E_{k2}(m_2)}$.
3. From the power property of Paillier encryption, this should be the same as: $E_{k1}(E_{k2}(m_1)\cdot E_{k2}(m_2))$.
4. From the homomorphic property, this is $E_{k1}(E_{k2}(m_1 + m_2))$.
5. I thought that decryption of the above expression, first with the corresponding private key of $k_1$ and then with that of $k_2$ should give $m_1 + m_2$.

First of all, if you see any problem in my construction, or if you can see another way to do it - please explain.

I tried to run this procedure using two implementations I found on the Web, but I got wrong results.

What am I doing wrong? Is it possible at all?

• Even if the result of step 2 "should be the same as" the value in step 3, step 3's result will always be less than $(n1)^2$ and step 2's result will usually be bigger than $(n1)^2$.) $\;$ Similarly, the value in step 3 will usually not be the value in step 4. $\;\;\;\;$ – user991 Apr 28 '15 at 19:26
• @RickyDemer Thanks for the comment. About your first sentence: I think that if I use $k_1$ which is twice longer (in bits) than $k_2$ (and so $n_1$ relatively to $n_2$), then it should be fine. About the second: I don't understand this. I know that the values will be different, as the encryption is random. I can't see why this is not a valid encryption of $(m_1 + m_2)$. Can you explain? – Gari BN Apr 28 '15 at 20:00
• Let the public key be $\: \langle 35,\hspace{-0.03 in}2\rangle \:$, $\:$ let the messages be 5 and 6, and let both random exponents be zero. $\;\;\;$ The ciphertexts for those messages will be 32 and 64, and $\: E_{\langle 35,2\rangle}(5\hspace{-0.04 in}+\hspace{-0.04 in}6) = E_{\langle 35,2\rangle}(11) < 35^2 = 1225 < 2048 = 32\hspace{-0.04 in}\cdot \hspace{-0.04 in}64 \;$. $\;\;\;\;\;\;\;\;$ – user991 Apr 28 '15 at 20:19
• @RickyDemer What about modulu? And how does this fit with the homomorphic properties mentioned in: en.wikipedia.org/wiki/… ? – Gari BN Apr 28 '15 at 20:37
• The modulus is what makes $E_{\langle 35,2\rangle}(5\hspace{-0.04 in}+\hspace{-0.04 in}6)$ not equal $\: E_{\langle 35,2\rangle}(5) \cdot E_{\langle 35,2\rangle}(6) \;$. $\hspace{1.47 in}$ Decryption includes the modulo operation. $\;\;\;\;$ – user991 Apr 28 '15 at 20:46

A ciphertext in Paillier is $g^m\cdot r^n\bmod{n^2}$. The plaintext space is the multiplicative group of integers modulo $n$. So, for it to even have a chance to work, first of all, the modulus of the outer encryption would have to be greater than $n^2$, where $n$ is the modulus of the inner. Assume this is true. Let the moduli be $n_i$ and $n_o$ for the inner and outer encryptions respectively (and $n_o > n_i^2$ (I'll similarly subscript all the other parameters).
So, for the encryption of $m_1$ we get $g_o^{g_i^{m_1}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Now, what we want is something like $g_o^{g_i^{m_1+m_2}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Possible options to get there include exponentiating the first by $m_2$, but that doesn't work. We could multiply the first by encryption of $m_2$ with the outer key, but that doesn't work. Even multiplying by the double encryption (first with inner, next with outer) doesn't work.