2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can the third party interact with the 2 users? Some sort of interaction is likely to be required. $\endgroup$ – mikeazo Feb 19 '17 at 12:36
  • $\begingroup$ The third party plays two roles, collects encrypted attributes from the two users and then to find common/duplicate attributes among the encrypted attributes without decrypting them. $\endgroup$ – CoolBird Feb 19 '17 at 13:33
  • $\begingroup$ Deciding properties of encrypted attributes without hints from users that encrypted them (or without decryption key holder) would be a problem. For example, a user can prove the same attribute is encrypted in two different ciphertexts. $\endgroup$ – Vadym Fedyukovych Feb 19 '17 at 13:42
  • $\begingroup$ So why did you choose to go down the homomorphic route? Is there a specific need for homomorphic? $\endgroup$ – mikeazo Feb 19 '17 at 13:50
  • $\begingroup$ TL;DR: no because Pailier is IND-CPA. $\endgroup$ – SEJPM Feb 19 '17 at 16:42
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot SEJPM, since, in our scenario we trust the data owners (clients), hashes will work for us. I would appreciate If you could plz suggest a good deduplication scheme (paper). Thanks once again. $\endgroup$ – CoolBird Feb 24 '17 at 6:40

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.