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:


Calculate $E_{k2}(m_2)$.
Calculate $E_{k1}(E_{k2}(m_1))^{E_{k2}(m_2)}$.
From the power property of Paillier encryption, this should be the same as: $E_{k1}(E_{k2}(m_1)\cdot E_{k2}(m_2))$.
From the homomorphic property, this is $E_{k1}(E_{k2}(m_1 + m_2))$.
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?
No, this is not possible. The homomorphism only works at one layer.

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 &gt; 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.

I know this isn't a rigorous proof, but there doesn't seem to be a way. The algebraic structure is just too mangled after a second encryption for it to work.