Is an equality test possible when using paillier crypto?

Question

Given two ciphertexts $c_1=Ek_1(p_1)$ and $c_2=Ek_2(p_2)$ encrpted by two different users with two different keys, i.e. $Ek_1$ and $Ek_2$ using a homomorphic crypto such as Paillier. Can a third party perform an equality test on $c_1$ and $c_2$ without knowing the keys?

As for my research efforts…

I read few papers on equality tests, and homomorphic encryption. However, in those papers almost all the scenarios are like when a client upload its encrypted data on the cloud and then search an encrypted keyword on it. In my case, I have a shared table of cipher texts and i have to find common attributes among the cipher texts encrypted by different clients stored in shared database. whereas normally comparison is made on cipher texts encrypted by a single client and done by the owner of the data.

Answer 1

No, you can't let a party test for equality with different keys without also allowing that party to guess and confirm the message contents.

I'll now show that a scheme that allows you to test for equality is trivially insecure against passive eavesdropping adversaries.

Suppose we're in the usual multiple-message eavesdropper game, that is our challenge messages actually are allowed to consist of multiple messages and we get the pair of individual encryptions as our challenge ciphertexts and are not allowed to ask the oracle for encryptions or decryptions.

1. Select $m_0=(m, m)$ and $m_1=(m, m')$ where $m\neq m'$.
2. Receive $c_b=(c,c')$ with $b\in\{0,1\}$ being chosen uniformly at random.
3. Use your special functionality "$=$" to evaluate $c=c'$. If it is true, return $b=0$ and if it is not return $b=1$.
   Note that this special functionality may involve choosing a key for the cryptosystem yourself and encrypting $m$ and $m'$ under that key you know and which is unrelated to the key used for $c,c'$.

Obviously, this strategy works with the same probability with which you can detect duplicates, which is $1$ which is non-negligible and as such this scheme cannot be secure against eavesdroppers who can observe multiple messages and make this equality test.

Note that Paillier-Encryption is IND-CPA secure, meaning it is secure in the above scenario even when you'd be given a way to encrypt messages and as such Paillier-Encryption cannot possibly allow for passive equality tests without being given the decryption key.

---

The best technical solution I could offer for your problem is to let each party encrypt the hash of the contents for the storage provider and then let the provider make the deduplication based on these hashes which only he can read. But this bears the problem that the users can of course lie about the hash because you have no way of verifying it. Alternatively you could run Socialist-Millionaires-Protocols between all pairs of files (well their owners should) and you use the reported results (if they agree) for deduplication which again relies on the honesty of the users.