# Equality check in homomorphic encryption

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.

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.