Comparison of values in Paillier homomorphic encryption

Question

For a project, I am using homomorphic encryption with the Paillier cryptosystem, and I have to compare two values...

• Can this be done using homomorphic encryption?
• And I know subtraction can be done using homomorphic encryption, but can anyone simplify the steps?

Any advice will be helpful.

Answer 1

Can [comparison] be done using homomorphic encryption?

Not without interaction with the person with the private key.

Suppose there was a possible way; given $E_k(a)$ and $E_k(b)$, one could determine whether $a < b$. If so, then one could use that to decrypt - given $E_k(a)$, one can encrypt various values of $b$ and then check whether $a < b$ or not - when we find a value $b$ such that $a < b$ and $a \not\lt b-1$, then we know the value of $a$.

Now, another possible meaning of comparison is, given $E_k(a), E_k(b)$ create $E_k(0)$ if $a < b$ and $E_k(1)$ if $a \ge b$. In that case, Pallier along with that comparison operation becomes fully homomorphic; for example, to compute the NAND of $E_k(a)$ and $E_k(b)$, one just compares $E_k(1-a)$ (easily computed with Pallier) to $E_k(b)$ - once we have a homomorphic NAND function, we can construct any circuit.

And I know subtraction can be done using homomorphic encryption, but can anyone simplify the steps?

Given $E_k(b)$, we can compute $E_k(-b)$ simply by computing the modular inverse of $E_k(b)$ - that's because $E_k(b) = g^b r^n$ and so $(E_k(b))^{-1} = g^{-b}(r^{-1})^n$, which is a valid encryption of $-b$.

Then, we can do the normal homomorphic addition to compute $E_k(a - b)$