2
$\begingroup$

We have $E(a)$, $E(b)$ encrypted under the same Paillier key.

As we all know, we can get $E(a+b)$ by calculating $E(a)*E(b)$.

But can we get $E(a-b)$, by calculating $E(a)/E(b)$?

I tried to calculate $E(a)/E(b)$ by using the mpz_divexact function in the GMP library. But I cannot get the correct result.

$\endgroup$
  • 1
    $\begingroup$ If I get a chance I'll write-up an answer here, but check out the wiki article from thep on negative numbers. Full disclosure: I wrote the article and thep. $\endgroup$ – mikeazo Oct 3 '14 at 18:36
  • $\begingroup$ @mikeazo Thank! I solve it under your instructions! I first calculate the inverse of E(b) and multiply it to E(a). $\endgroup$ – Jan Leo Oct 3 '14 at 19:14
4
$\begingroup$

In Paillier, as you note, multiplication in the ciphertext domain translates to addition in the plaintext domain. Thanks to the algebraic structure behind Paillier what you can do to get subtraction is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what decryption will return is something between $0$ and $n-1$. For example, if the result is $-1$, you will see $n-1$. To deal with this, we can set some threshold (will depend on the application). If the decrypted value is greater than that threshold, return that value minus $n$. For example, if we see $n-1$ on decryption, we will return $n-1-n=-1$.

$\endgroup$
1
$\begingroup$

It's pretty simple. $E(a-b) \equiv E(a)\cdot E(b)^{-1} \pmod{N^2}$.

$E(b)^{-1}$ is the multiplicative inverse of $E(b)$ modulo $N^2$.

$\endgroup$
0
$\begingroup$

I'll just add that $E(a)/E(b)$ is correct, i.e. $E(a)\cdot E(b)^{-1}$, and the inverse $\bmod n^2$ is given in libgmp via the mpz_inverse function.

However, that's not the only way. You can also do $E(a)\cdot E(-b)$. The reason why that may be convenient is because $E(b+...+b)$ ($n$ times) is easy to calculate, being $E(b)^n$, and so there is an exponentiation function mpz_powm that comes in handy, and either you can try using it with a negative exponent (I don't know what will happen) or you can use $N-1$, where $N$ is the order of $E(b)$ in the multiplicative group. Fermat's little theorem says $N=pq(p-1)(q-1)$ for modulus $n^2$ with $n=pq$.

Unfortunately the public key is $n=pq$, and $p+q$ (which you need) is unknown. So one has to munge that a bit. I've tried using $n^2-1$ instead of $N-1$, and it seems to work but surely it can't in general.

I'd rather trust to going from $A(p-1)(q-1)=1+Bpq$, that is $A$ is the inverse of $(p-1)(q-1) \bmod n$, $n=pq$. Then $Apq(p-1)(q-1)=n+Bn^2$, so $E(b)^{n+Bn^2}=1 \bmod n^2$, and $E(b)^{n+Bn^2-1} = E(b)^{-1} \bmod n^2$. I don't think supplying $B$ as an extra part of the public key does any harm. But I Am Not A Cryptographer.

$\endgroup$

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.