Is it reasonable to consider that an encryption scheme must be invertible?

Question

I am in a dispute regarding a test question in an exam. The question is something like that:

What would happen if one were to use RSA with $n=100$ and $e=13$ to encrypt a message $m$?

a) You would be able to encrypt the message but not decrypt it.

b) You would not be able to encrypt the message.

...

Both parties agree that the operation $c = m^e \bmod n$ (a transformation known as encryption when using proper RSA) is no longer bijective, as $n$ is not the product of two primes. For example, $m=10$ and $m=20$ would both result in "cryptogram" $c=0$.

I consider that an encryption function must be invertible, as the purpose of encryption is to hide information from non-authorized eyes while allowing authorized parties to retrieve it. The fact that this transformation (which I'd argue could not even be called RSA, as $n$ does not fulfill RSA's rules) is not bijective means that it is not invertible, so it cannot be considered encryption. I would say that, under this assumption, any discussion of encryption/decryption is pointless, and if one answer had to be marked, it should be B: we cannot call $c = m^e \bmod n$ "encryption".

On the other hand, the other party sustains that the only correct answer is A, and that "it is fallacious to believe that encryption must be invertible, as there are many non-invertible encryption schemes". They are not available for questioning, so I cannot seek further clarification about what they meant. I assume they meant cryptographic hashes, but I would not consider them encryption schemes, but cryptographic primitives.

My question is therefore two-fold:

1. Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?
2. If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?
3. If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?

Answer 1

1. Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?

Yes, strictly speaking: Encryption is the process of turning a plaintext message into a ciphertext (encryption) which then can later be turned back into the original plaintext (decryption).

---

2. If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?

Gary Kessler has published An Overview of Cryptography.

In chapter 3 "Types of cryptographic algorithms" you can see that there is a distinction drawn between encryption and hash functions.

---

3. If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?

Encryption, decryption and cryptographic hashes all belong together in the realm of cryptography but they can definitely not be used interchangable (see this earlier answer from a different question). Some differences include:

Reversability

Encryption schemes can usually be transformed back into their original form, i.e. a once encrypted plaintext message can usually be decrypted back into the original plaintext. Hashes, on the otherhand, are created in a manner that the input undergoes a loss of information, ultimately making it irreversible.

You can always create a hash from a given input but it's not possible to be sure what the original message once was if you're only given the hash (see pigeonhole principle).

Keys

Encryption schemes always use keys. Hashes do not require keys.

Length

A long plaintext message results in a long encrypted ciphertext & a short plaintext message results in a short encrypted ciphertext.

Hashes will always have a predefined length, no matter the input.

Answer 2

Note that the notion of invertibility that you discuss is called the correctness of the encryption scheme. Your question is essentially "Are incorrect encryption schemes still encryption schemes?" I would argue no, for the following reasons.

An encryption scheme is generally defined as a triple of algorithms $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$. These have three sets associated with them --- $\mathcal{K}$ the key space, $\mathcal{M}$ the message space, and $\mathcal{C}$ the cipher space. The type signatures of these functions are:

\begin{align} \mathsf{KeyGen} &: 1^\mathbb{N}\to \mathcal{K}\\ \mathsf{Enc} &: \mathcal{K}\times \mathcal{M}\to\mathcal{C}\\ \mathsf{Dec} &: \mathcal{K}\times\mathcal{C}\to\mathcal{M} \end{align} The above are all usually randomized as well (which I haven't written for simplicity). Don't worry too much about $1^{\mathbb{N}}$ --- this just means "We input some number which represents 'how hard' we want the scheme to break" (such as how many bits to use in our RSA instance). You should read the above as saying that:

1. Keygen outputs keys
2. Encryption takes a key and message, and outputs a ciphertext
3. Decryption takes a key and ciphertext, and outputs a message

These algorithms must all be efficient (there are many candidate notions of efficiency). There are generally two additional requirements these algorithms must satisfy:

1. Correctness: This is what you're interested in. One basic version (which suffices for many purposes) is perfect correctness: $$\forall k\in\mathcal{K}, \forall m\in\mathcal{M} : (\mathsf{Dec}_k\circ\mathsf{Enc}_k)(m) = m$$

2. Security: This can be formalized in many ways. All of them have some underlying intuition that "It's computationally hard to derive even partial information about the plaintext underlying a ciphertext without the key".

---

One might ask then "Are incorrect encryption schemes useful?" The answer is no, for the following reason. Imagine that $0$ is a valid ciphertext (you can replace this with any other constant value $c\in\mathcal{C}$ that you want). Then, for any sets $\mathcal{M}, \mathcal{K}$, we can define an (incorrect) encryption scheme which is:

1. Incredibly efficient
2. Perfectly secure
3. Of very good parameters --- ciphertexts are quite small, keys are quite short compared to messages, etc

This is done by setting $\mathsf{Enc}_k(m) = 0$ for all $m$.

Now, you might remember a classical result on perfectly secure encryption schemes.

(Shannon): Let $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ be a perfectly secure encryption scheme with key space $\mathcal{K}$, message space $\mathcal{M}$, and cipher space $\mathcal{C}$. Then $|\mathcal{K}| \geq |\mathcal{M}|$.

This is the underlying motivation of all computational notions of security. It's also false if one allows encryption schemes to be incorrect (the aforementioned "constant encryption scheme" can be made to arbitrarily beat Shannon's bound).

So while the question of "Is an incorrect encryption encryption scheme still an 'encryption scheme'" reduces to individual preference, if one wants to accept the above form of Shannon's result (which I imagine essentially everyone does) there is one right answer --- encryption schemes must be correct.

I bring up the Shannon example as most introductory cryptography courses cite some form of the above theorem. You can likely use this as a reference to the requirement that encryption schemes are correct.