# Comparison of values in Paillier homomorphic encryption

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?

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

• Let's say I have a msg m1 and it is in encrypted form, and I have another predefined value say K. I want to compute how close m1 is within the predefined value K. How can it be done? Which keys would I be needing? I am a beginner – dsaharia Jul 6 '19 at 13:45
• @dsaharia: you can compute $E( m1 - K )$ and $E( -(m1 - K))$; however that's about the best you can do... – poncho Jul 6 '19 at 13:47
• I want to determine the closeness of m1 with regards to another value. How can this be done? – dsaharia Jul 7 '19 at 7:30
• Also you can use the ability to compute the difference between two ciphertexts to at least test for equality. Given a random group element $d$, you can compute $E_k(a-b)^d$ and send that off for decryption. Decrypting will reveal whether or not $a==b$ and nothing else since it is blinded by the additional multiplicative factor. Explicitly, the difference between $a$ and $b$ equals zero iff $a==b$. Any other value will be randomly altered by the multiplication while zero is untouched. – Ken Goss Oct 2 '19 at 15:00