2
$\begingroup$

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}$

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user153465
    Commented Aug 5, 2016 at 14:13
  • 1
    $\begingroup$ 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... $\endgroup$
    – poncho
    Commented Aug 5, 2016 at 14:38
  • $\begingroup$ @poncho, the question explictely states that $r_i^{-1}\in\mathbb Z_n$ so my answer is correct with respect to that question :) $\endgroup$
    – SEJPM
    Commented Aug 5, 2016 at 14:41
  • $\begingroup$ Yep, you're right; he's shifting the question... $\endgroup$
    – poncho
    Commented Aug 5, 2016 at 14:53

Your Answer

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

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