Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
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$.
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.
