1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Apr 28, 2015 at 19:26
  • $\begingroup$ @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? $\endgroup$
    – Gari BN
    Apr 28, 2015 at 20:00
  • $\begingroup$ 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 \;$. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Apr 28, 2015 at 20:19
  • $\begingroup$ @RickyDemer What about modulu? And how does this fit with the homomorphic properties mentioned in: en.wikipedia.org/wiki/… ? $\endgroup$
    – Gari BN
    Apr 28, 2015 at 20:37
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Apr 28, 2015 at 20:46

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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