In Paillier homomorphism how do you substract?

I'm trying to learn homomorphism so the problem may also be in my code (which I will include).

I want to compute $a - b$ where $a$ is bigger then $b$. In order to do this I tried to compute $\frac{a}{b}$. However when I decrypt this I get garbage. Or ciphertext $c$ is not in $\mathbb{Z}^{*}_{n^2}$.

Now because the problem may also be in my code here it is:

import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws Exception{
Paillier pp = new Paillier (2048);
BigInteger a=pp.encrypt(BigInteger.valueOf(100000));
BigInteger b=pp.encrypt(BigInteger.valueOf(10000));
BigInteger c=a.divide(b);
c=c.remainder(pp.getNsquare());
BigInteger res=pp.decrypt(c);
System.out.println("res = "+ res);
}
}

And I used this library

I also tried to see what happens if you multiply $b$ with $-1$ but that just gave me garbage. Anyone know how to do this?

So so far I tried

• $c = \frac{a}{b}$ which tends to result in $c=0$ and unable to retrieve $c$
• $c+2^{2047}=\frac{a \times 2^{2047}}{b}$ which results in $c$ is a large number and $c$ is negative some larger number
• $c+2^{2047}=\frac{a \times 2^{2047}}{b}$ inverse mod $N^2$ which results in $c$ is a large number and $c$ is negative some larger number
• $c+2^{2047}=\frac{a \times 2^{2047}}{b}$ remainder $N^2$ which didn't decrypt.

Is this a problem in my code or in my understanding of crypto?

• I hope this is not something overly trivial, I have mostly a machine learning background and crypto is still a bit hard to follow. Jun 27 '16 at 5:12
• The problem is neither in your code nor in your understanding of "crypto", it is in your understanding of mathematics. As with way too many people here, I shall add. Jun 27 '16 at 5:26
• @fkraiem alight what am I doing wrong in terms of mathematics? And isn't crypto just applied mathematics? Jun 27 '16 at 5:28
• By the way @fkraiem I have updated some of my math does it make sense to you? Jun 27 '16 at 10:28

Let $c_a$ be the encrypted version of $a$, and $c_b$ be the encrypted version of $b$. What you want to compute is $c_c$ which is the encrypted version of $a-b$, so that when you decrypt $c_c$ you get $c=a-b$.

Paillier supports a homomomorphic addtion of ciphertexts to get an encrypted version of the sum. The actual mathematical operation it takes to get this is modular multiplication. In otherwords, multiplication in the ciphertext domain results in addition in the plaintext domain.

Paillier also supports multiplication of a ciphertext value and a plaintext value. This is achieved by modular exponentiation.

To achieve what you want here, you need to negate $c_b$ by multiplying by $-1$ in the ciphertext domain. To achieve this operation (an encrypted negation of $b$, given only the encryption of $b$, $c_b$), you would do $c_b^{-1}\bmod{n^2}$. That would given you an encryption of $-b$. You homomorphically add that value to $c_a$ (which is achieved via modular multiplication on the ciphertexts) to get $c_c$.

I have an example of subtraction in Paillier in the library I wrote. I also had a writeup about negative numbers in Paillier you may find interesting at the old Google Code host.

• Isn't c^-1 mod n^2 going to be 0 though? I mean c>1 (it's an int) so what prevents c^-1 from going to zero especially given that c is also an int? Jun 27 '16 at 12:25
• You are suppose to do modular exponentiation which is very different from regular exponentiation followed by a mod. This is why libraries such as BigInteger have a pow operation and separate modPow. They are very different operations, expecially when we start talking about negative exponents. Jun 27 '16 at 12:53
• Thank you! That explained what I was doing wrong. So it was a mixture of math crypto and code failure. Thank you! Jun 27 '16 at 12:59

In Pailler encryption, it holds for all messages $a$ and $b$ and whatever the random number used by encryption that: \begin{align} (a+b\bmod n)&=D(E(a)\cdot E(b)\bmod n^2)&&\text{and}\\ (a-b\bmod n)&=D(E(a)\cdot E(b)^{-1}\bmod n^2) \end{align} where the modular inverse $E(b)^{-1}$ is computed modulo $n^2$, that is in $\Bbb Z_{n^2}^*$.

If $0\le b\le a<n$ then the left $\bmod n$ in the second equation can be removed and we get $a-b$.

Otherwise, we can define a modified decryption working for small signed numbers, as: $$D'(x)=((D(x)+\lfloor n/2\rfloor)\bmod n)-\lfloor n/2\rfloor$$ and then assuming $-n/4<a<n/4$ and $-n/4<b<n/4$, we have: \begin{align} a+b&=D'(E(a)\cdot E(b)\bmod n^2)&&\text{and}\\ a-b&=D'(E(a)\cdot E(b)^{-1}\bmod n^2) \end{align}