1
$\begingroup$

Is there a scheme where two ciphertexts (encrypted with different keys) can be proven to have the same (plaintext) content without disclosing the plaintext or any private keys? I assume that the public keys would need to be known.

This is for the purpose of detecting duplicated content on a server, without knowing the content.

This is probably impossible, but reading about homomorphic encryption leads me to think that it might be possible.

$\endgroup$
0
1
$\begingroup$

Yes, this is known as convergent encryption.

The usual way to do it is content hash keying, where you hash the plaintext, then use that hash as a key for deterministic symmetric encryption. You get authentication "for free" by checking that the hash matches, though that means the ciphertext is unauthenticated and you probably want to avoid modes like CBC with its padding attacks.

The symmetric key can in turn be encrypted using one or more long term keys (symmetric or asymmetric). That way only the encrypted keys need to be stored for every user, but the encrypted data itself can be deduplicated.

The limitations mentioned in the other answer are real. The server or anyone observing its space use and processing can tell that two users encrypted the same piece of data. You can also verify whether the ciphertext matches a plaintext guess. This does not make the encryption useless, but is something you have to take into account.

$\endgroup$
2
$\begingroup$

Consider that I, as an attacker, suspects what you're sending in your secret messages. If what you propose were possible, then I could know your plaintext by comparing my encryption of what I thought you were sending to what you actually sent, and brute for variations until I could confirm what you had sent. This would be VERY bad. Therefore, I assume you understand why I hope what you want is impossible as you proposed.

What could be done, would be to hash the message before encrypting it, and then comparing the hashes... this would again, especially with rainbow tables, lead to what I said above... the ability to know the message without decrypting it.

$\endgroup$
2
  • 1
    $\begingroup$ The idea is probably to accept that loss of security, just like users of homomorphic or deterministic encryption have to accept some weaknesses to be able to manipulate/compare encrypted data. $\endgroup$
    – otus
    Nov 19 '15 at 9:36
  • $\begingroup$ Yes, I don't care if an attacker can confirm the contents of the message if the attacker already knows the content or has a hash of it. $\endgroup$ Nov 19 '15 at 9:46

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.