In Paillier homomorphism how do you substract?

Question

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?

Answer 1

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.

Answer 2

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