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 at 3:40
  • 2
    $\begingroup$ Little intro here Advantages and possible usages of encryption schemes with probabilistic decryption $\endgroup$ – kelalaka Mar 5 at 7:29
  • $\begingroup$ Are we in the symmetric-key or the public-key setting? $\endgroup$ – Occams_Trimmer Mar 8 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$ – Occams_Trimmer Mar 8 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$ – Occams_Trimmer Mar 8 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.