1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – dsaharia Jul 6 at 13:45
  • $\begingroup$ @dsaharia: you can compute $E( m1 - K )$ and $E( -(m1 - K))$; however that's about the best you can do... $\endgroup$ – poncho Jul 6 at 13:47
  • $\begingroup$ I want to determine the closeness of m1 with regards to another value. How can this be done? $\endgroup$ – dsaharia Jul 7 at 7:30
  • $\begingroup$ 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. $\endgroup$ – Ken Goss Oct 2 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.