In a modern secure encryption scheme, is it possible(both theoretically and practically) to encrypt a message using a key to get the following ciphertext c = Enc(M1,k1) and later find another key so that a different message of my choice gets encrypted to the same ciphertext c = Enc(M2,k2)?

  • 5
    $\begingroup$ Yes, this is possible. It goes by the name of "Deniable Encryption", and was introduced in this paper. I am not up to date on the relevant literature, so cannot survey the current state of the art (hence why this is a comment). $\endgroup$
    – Mark
    Mar 5, 2021 at 3:40
  • 2
    $\begingroup$ Little intro here Advantages and possible usages of encryption schemes with probabilistic decryption $\endgroup$
    – kelalaka
    Mar 5, 2021 at 7:29
  • $\begingroup$ Are we in the symmetric-key or the public-key setting? $\endgroup$
    – ckamath
    Mar 8, 2021 at 16:53
  • 1
    $\begingroup$ In the symmetric-key setting this is easy to achieve. E.g., doesn't the one-time pad satisfies this property? In general, XOR-based stream ciphers (i.e., ones which take the message and XORs with a pseudo-random steam) satisfy this property. This is, in fact, used in protocols like TextSecure and Off-the-Record Messaging. You can read more here and here. $\endgroup$
    – ckamath
    Mar 8, 2021 at 21:52
  • 1
    $\begingroup$ "[...] the public key is known to everyone and this might make it impossible to change the secret key". True, therefore one needs to take the randomness used to encrypt in account. That is, given a ciphertext $c=E_{pk}(m;r)$ can one find $m'$ and $r'$ such that $c=E_{pk}(m;r)$ (let's focus on a single public key for now)? Such $(m',r') exists for example in El Gamal encryption, but are not necessarily easy to find. This is where deniable encryption (a Mark points out) comes in. These are far from practical though. $\endgroup$
    – ckamath
    Mar 8, 2021 at 22:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.