Is it possible to get different plaintexts from a single ciphertext using different keys?

Question

Suppose to have a chipertext that you can't decrypt, but you know that the plaintext can be A, B or C. Then arrives to you the key which is used to encrypt the chipertext. You can decrypt the chipertext and you get a plaintext equal to A. Is it possible that the original plaintext was B or C and you have received a key such that the decryption process gives as output a different plaintext (A)?

Of course, each A, B and C have a meaning to you, so if you decrypt something else (like D, E, F...) you understand that it is meaningless. Also, i want to add that the source from which you receive the key cannot be trusted, but this doesn't mean that the key is always incorrect.

For clarification:

1. I receive a ciphertext I can't decrypt
2. I receive a key to decrypt the ciphertext
3. I decrypt the ciphertext with the key from step 2 and get the plaintext

How can I be sure that the plaintext obtained is infact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

Answer 1

How can I be sure that the plaintext obtained is in fact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

In general you cannot. The standard security notions of do not imply any binding. I.e., the definitions do not rule out that, given a key $k$ and a ciphertext $c \gets \operatorname{Enc}(k,m)$ an attacker might be able to find a key $k'$, such that $m' = \operatorname{Dec}(k',c)$ for some $m' \neq m$. In fact, for many encryption schemes, such as block ciphers in some non-authenticated mode of operation, or a stream-cipher this is always possible, since decryption will always succeed with any key. What differs between different schemes is how much control an attacker may have over $m'$. But for many schemes some control, such as ensuring that a few bits have specific values is certainly possible.

Opening an encryption scheme to a different value than was originally encrypted is called equivocation. The one-time pad as described by AleksanderRas is an extreme of an equivocal encryption scheme, being *fully equivocal. I.e., for any ciphertext $c$ and any plaintext $m'$ it is possible to find a key $k'$, such that $\operatorname{Dec}(k',c)=m'$. Being equivocal is in fact a useful property of an encryption scheme in applications such as secure multi-party computation. However, being fully equivocal actually implies the scheme must necessarily have a key size which is as large as the message size. There are relaxed notions of somewhere equivocal and non-committing encryption.

That name of that last notion brings us to the fact that you do in fact want your encryption scheme to not be equivocal. The opposite of an equivocal encryption scheme would be a committing encryption scheme, where the ciphertext serves as a commitment to the plaintext.

At this point your question and in particular the "key-exchange" tag lead me to believe that you are probably not actually looking for an encryption scheme, but a commitment scheme. A commitment scheme allows one party to commit to a message $m$ in a commitment $c \gets \operatorname{Com}(m;r)$. Such a commitment can later be opened usually by revealing the randomness $r$ used in the commitment.

A commitment scheme has two important properties:

1. It is hiding, meaning that $c$ reveals nothing about $m$.
2. It is binding, meaning that it is infeasible to equivocate, i.e., to open the commitment $c$ to a message $m'\neq m$.

Answer 2

It is indeed possible (as Maeher correctly pointed out) to have such a property.

Probably the most known encryption system with this property is the one-time pad. It has some limitations, like the key has to be (cryptographically secure) random and the same length as the plaintext.

Procedure:

1. Encrypt a message $m_1$ with key $k_1$
2. Now we have a ciphertext $c$

3. It's now possible to decrypt the ciphertext $c$ with:

   a. The (correct) key $k_1$ and get the resulting message $m_1$

   b. The (incorrect) key $k_2$ and get a different message $m_2$

The problem is, that we can not be sure which key was originally used to encrypt the message $m_1$, because both decryptions could be valid (= make sense).

Let's directly take the example from Wikipedia:

1. Alice want's to send a message ($m_1$) to Bob

   HELLO

2. She chooses the key ($k_1$)

   XMCKL

3. By using modular addition (see the example in wikipedia if this step is unclear) we get the ciphertext $c_1$

   EQNVZ

4. Bob can now decrypt the ciphertext $c_1$ with the key

   a. $k_1$ (XMCKL) and obtain the intended plaintext message $m_1$

   HELLO

   b. $k_2$ (TQURI) and obtain a different message $m_2$

   LATER

This is possible because both the word HELLO and LATER have 5 characters. It's actually possible to decrypt any ciphertext ($c_1$) to any given plaintext ($m_n$) with the same length.