I need to prevent Mallory from blindly matching encryption and signing keys to messages

Hypothetical scenario:

  1. A user creates a public key
  2. An encrypted or signed payload exists.
  3. With only public key, and a signed or encrypted payload, Mallory wants to find out who signed the data. We want to prevent Mallory from associating an encrypted payload to the public key.

I assume that most modern encryption primitives (GCM, AES, RSA, Blowfish) allow for this type of association, however, it's possible that some protocols (GSM?, SMIME? PGP?) might disclose the signing key in the payload, even if the spec allows its omission.


Can someone either tell me which crypto allows for plausible deniability, or conversely which ones do not?*

*I ask in this way to prevent a too broad close reason, because I'm not sure which is greater

Additional Info:

  1. Mallory has the public key, so CPA attacks might be possible, but the data should be random.
  2. It is acceptable that the original signer, and intended recipient can verify the key.
  3. If Mallory somehow MITMs the connection, and passes her key to the signer, plausible deniability doesn't have to apply.
  • Suggestions on tagging and re-phrasing this question appreciated. Jan 7, 2015 at 20:05
  • I recently asked (not very well!) a question that partly overlaps yours. My answer there gives an example of a protocol that might also have worked as an answer to your question. Apr 21, 2016 at 13:07

2 Answers 2


If it is encrypted, just knowing the public key it may be possible to conceal the key that was used. As the public key will just be encrypting a random key for a symmetric cipher, a large enough key length means it can't be bruteforced. The owner of the private key simply decrypts the key and tries if the data is properly decrypted (eg. an attached hmac). Mallory simply can't test all possible keys.

On the other hand, if the data is signed, by its very definition it must be possible to verify that key A signed data. So Mallory could always determine which of the public keys it has signed that file. (OTOH if Mallory doesn't have your key or eg. a database with the keys from every suspect, even on schemas that contain "metadata" it typically only provides the fingerprint of the key used, so it's useless)

The simple answer is to encrypt(sign(data)).

Obiously, the metadata -such as sending email account- shouldn't be leaking your identity.

This only achieves plausible deniability for the given scenario of blindly matching keys to messages. Bob would be perfectly able to prove that the message he received was sent by Alice. Usually, the term plausible deniability is used to mean that Alice can even deny that she wrote that. For that you can use a protocol like OTR.


Is not the solution to encrypt with the recipient's public key?

Anybody could have written it but only the intended receiver can read it.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .