Considering that we have a homomorphic encryption server working with integers mod p (a large prime number) with access to multiplication, addition and subtraction, is it possible to design an equality function which receives two encrypted values and returns an encrypted 1 if they are equal and an encrypted 0 if they are different?

This is obviously assuming randomized encryption, so direct comparison of the ciphertexts would be impossible.


Depends on what you mean "returns 1 if there are equal".

If you mean "returns an encrypted 1 if there are equal, and 0 if there are not", then here's one straight-forward way; to compare the values $A$ and $B$, you just compute the encrypted value $1 - (A - B)^{p-1}$; that is an encrypted 1 if $A = B$ (because $A - B = 0$), and an encrypted 0 if $A \ne B$ (Fermat's Little Theorem). This takes $O(\log p)$ homomorphic multiplications, and two homomorphic subtractions.

On the other hand, if you mean "returns the value 1", and so allows someone without the private key whether two values are the same, we hope that's not possible. That would be a violation of the security of the system; it would allow an adversary to determine the value of encrypted plaintexts, and so if it were possible, the homomorphic system would be insecure.

| improve this answer | |
  • $\begingroup$ Yes, I meant to return an encrypted 1 or encrypted 0 and edited the original question to reflect it. This solves it! Thank you $\endgroup$ – onaheimi3 Apr 2 '18 at 22:26

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.