1. $A$ sends $B$ the encryption $E_{pkA}(m)$.
  2. $B$ computes $R=xE_{pkA}(m) + y$ and sends $R$ back to $A$, but tells him nothing about the parameters $x$ and $y$.
  3. $A$ performs $D_{pkA}(R)$ and recovers the value $xm+y$.

Is this protocol possible using the Paillier cryptosystem?


1 Answer 1


Yes (assuming $A$ knows the Paillier private key and $B$ knows the Paillier public key and the values of $x$ and $y$)

With Pallier, someone with the public key can:

  • Homomorpically multiply a ciphertext by a known value; that is, given $x$ and $E_{pkA}(m)$ compute $E_{pkA}(xm)$

  • Encrypt a known value; that is, given $y$, compute $E_{pkA}(y)$

  • Homomorphically add two encrypted values; that is, given $E_{pkA}(xm)$ and $E_{pkA}(y)$, compute $R = E_{pkA}(xm + y)$

The resulting $R$ value can be decrypted by $A$; $A$ cannot deduce anything other than the value $xm + y$


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.