# a homomorphic operation on Paillier encryption

Assume $N=pq$, where $p$ and $q$ are two strong prime numbers.

Also, assume we have finite field $\mathbb{F}_u$ where $u$ is a $112$ bit prime number. Let $r_i$ be a uniformly random element of $\mathbb{F}_u$.

Let $(r_i)^{-1}$ be multiplicative inverse of $r_i$ in ring $Z_N$.

We encrypt a message as $c=E(r\cdot m)$ using Paillier encryption.

Question 1: Given $c$ and $(r_i)^{-1}$, can we "always" perform $c^{(r_i)^{-1}}=E((r_i)^{-1}\cdot (r_i)\cdot m)$ such that its decryption value only contain $m$?

Question 2: given $E(m)$, how can we chose its additive inverse $m'$ such that $E(m).E(m')=E(m+m')$ so its decryption value would be 0? should $m'\in \mathtt{Z}_N$ or $m'\in \mathtt{Z}_N{^2}$

Question 1: Given $c$ and $(r_i)^{-1}$, can we "always" perform $c^{(r_i)^{-1}}=E((r_i)^{-1}\cdot (r_i)\cdot m)$ such that its decryption value only contain $m$?

Yes. You can multiply arbitrary values $x$ into a message using paillier encryption and it will result in multiplication $\bmod n$ and thus you'd get $m$ back.

This would happen by exponentiating the cipher text with the $x$, as $c^x\bmod {n^2}$ as you described.

Question 2: given $E(m)$, how can we chose its additive inverse $m'$ such that $E(m).E(m')=E(m+m')$ so its decryption value would be 0? should $m'\in \mathtt{Z}_N$ or $m'\in \mathtt{Z}_N{^2}$

I don't think there's any way given a ciphertext of $m$ to construct a plaintext $m'$ that would yield $m+m'=0$ as this would trivially equal a plaintext recovery and thus a (nearly) total break of the encryption.

However, you can use the answer from question one to calculate the additive inverse ciphertext, which would be $c^{n-1}\bmod{n^2}$. If you multiply this with the original cipher text, you will get an encryption of $0$, to which you can add whatever you want (e.g. an encryption of 1?).

Alternatively you might as well just exponentiate the ciphertext with $0$ to get the same result...

• Thank you for the answer. To clarify question 2: let ciphertext be $E(m+b)$, where $b$ is an element of the ring. I (as the person who knows $b$) can compute $-b$ , and then compute $E(m+b).E(-b)$, so when we decrypt we would get $m$. So I'm not trying to attack the encryption, I try to perform additive homomorphic operation. Aug 5, 2016 at 14:13
• Actually, he's not interested in computing $c \cdot r_i^{-1} \bmod n$; we wants to do it $\bmod p$, which appears to be a 112 bit prime unassociated with $n$. Actually, Pallier with that additional operation turns out to be fully homomorphic (!), and hence a discovery of such a method would be rather bigger news than whatever protocol he's trying to design via crowdsourcing... Aug 5, 2016 at 14:38
• @poncho, the question explictely states that $r_i^{-1}\in\mathbb Z_n$ so my answer is correct with respect to that question :) Aug 5, 2016 at 14:41
• Yep, you're right; he's shifting the question... Aug 5, 2016 at 14:53