8
$\begingroup$

I've seen that it's widely accepted that before Gentry's breakthrough (which is not practical yet) in 2009 there were no known full homomorphic encryption scheme.

I've read here in another answer that:

"...there are many known partially homomorphic cryptosystems, each one can either multiply or add numbers."

Now here on some interactive webpage allowing to test Paillier here:

mhe.github.io/jspaillier/

I can do [(A+B)*C], hence doing both addition and multiplication (?).

Why is Paillier not fully homomorphic seen that it can do both addition and multiplication?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ That site is somewhat confusing. C is not encrypted, there is no encrypt button. Paullier can add cithertexts, but only multiply by a plaintext. $\endgroup$ – mikeazo Jun 24 '14 at 10:15
  • 2
    $\begingroup$ You can only homomorphically add two ciphertexts, but you can only homomorphically multiply each ciphertext with a plain integer (this operation can also be seen as a more efficient way than doing a number of successive additions of a ciphertext). Note that the latter is not a homomorphic multiplication of ciphertexts (which you would require for the scheme to be fully homomorphic)! $\endgroup$ – DrLecter Jun 24 '14 at 10:18
  • $\begingroup$ @mikeazo: oh, ok... Didn't realize that: I've indeed been a bit confused by that little interactive demo. Makes a lot of sense. Thanks to both of you! $\endgroup$ – Cedric Martin Jun 24 '14 at 10:23
  • $\begingroup$ Could you accept and close this question? $\endgroup$ – kelalaka Sep 29 '19 at 21:35
8
$\begingroup$

It can not do multiplication in the plaintext domain using two ciphertexts. In other words, given $E(m_1)$ and $E(m_2)$, you can not get $E(m_1\cdot m_2)$. You can only get $E(m_1+m_2)$.

Given $E(m_1)$ and $m_2$, you can get $E(m_1\cdot m_2)$ however. But notice that $m_2$ in this case was not encrypted. On the site you reference, $C$ is not encrypted. It is using this feature that I just described.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I just wanted to add that this is not a special property of Pallier encryption. It is in fact a property of any additively homomorphic encryption scheme. This is because $m_1 \cdot m_2 = \Sigma_{i \in \{1, \ldots, m_2\}} m_1$. I.e., from $E(m_1)$ you can compute $E(m_1 \cdot m_2)$ by simply using the additively homomorphic property $m_2$ times. $\endgroup$ – Guut Boy Jul 29 '15 at 12:41
  • $\begingroup$ @GuutBoy, it is in fact partially a special property of Pallier, because the Ciphertexts permit multiplication by plaintext scalars without using repeated addition by raising $E(m)^k = E(mk)$ $\endgroup$ – Confused_Coder Aug 23 '18 at 5:16
  • 1
    $\begingroup$ @Confused_Coder well this is only because repeated use of the additvely homomorphic property is equivalent to exponentiation in the case for Pallier (because in Pallier we have roughly $E(m_1) \cdot E(m_2) = E(m_1 + m_2)$). Anyway, it does not change the fact that this is something that applies to any additively homomorphic encryption scheme. $\endgroup$ – Guut Boy Aug 24 '18 at 8:34
  • $\begingroup$ @GuutBoy based on my understanding of Pallier, the operation is computable via exponentiation, not just via repeated application of addition. There certainly could exist other additively homomorphic schemes where you would not be able to compute the scalar multiplication directly as with Pallier, but you could compute it via repeated addition. $\endgroup$ – Confused_Coder Aug 28 '18 at 4:05

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.