2
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ I sympathize with the point of view that b) is a correct answer for the (logical) reason stated in the question that if it's not reversible, it's not encryption. But I suggest that this person should consider a meta fact: with this line of thought, neither a) nor b) would be a correct answer. Therefore it is possible to infer from the context of this being an exam with two answers that the expected answer is a). Just shifting one's mind from making the correct answer to making the expected answer leads to the conclusion that one should tick a), and move on. $\endgroup$ – fgrieu Jun 22 at 13:06
  • $\begingroup$ My opinion is that $n=100$ disqualifies the scheme as encryption for a practitioner's definition of that because we can factor any $n$ not at least 200 decimal digits, thus the question is poor. But if instead I was defending the perspective that only a) is right (I'm not), I would point out that it is not unknown that textbook Rabin encryption ($x\mapsto y=x^2\bmod n$ where $n$ is the product of two secret distinct primes as in RSA) is considered encryption, even though there is in general four $x$ for any given $y$: only one would be meaningful, and that's how the issue is solved. $\endgroup$ – fgrieu Jun 22 at 13:17
  • $\begingroup$ @fgrieu A is a pretty common situation – you have just a public key and no private key. (Well, for short keys, it can be disputable, but that's another topic.) So, you cannot decrypt the message you have just encrypted, but someone else can. But this case is different, as nobody can decrypt the result, so I wouldn't consider A as a correct answer. Well, you technically can use the encryption formula, but the result is going to be useless for some $n, so I wouldn't call it encryption. $\endgroup$ – v6ak Jun 23 at 7:00
  • $\begingroup$ Moreover, the question is not quantitied and there are 40 values that you can encrypt and then decrypt. So, mathematically, the answer also depends on the value m, which is not provided. If your m is from {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99}, you can both encrypt and decrypt. So, the only mathematically correct answer is we cannot even decide if you can encrypt/decrypt. $\endgroup$ – v6ak Jun 23 at 7:07
4
$\begingroup$
  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).


  1. 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.


  1. 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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. I believe there are two different schools of thought, and the other party and myself belong to different ones. In the website you quote, encryption does not require invertibility, and would be part of the other party's school (for example, it states "Hash functions, also called message digests and one-way encryption" or "Hash Functions: Uses a mathematical transformation to irreversibly "encrypt" information" (note the quotes around "encrypt", though). $\endgroup$ – user2891462 Jun 22 at 12:43
  • $\begingroup$ On the other hand, resources such as "Handbook of Applied Cryptography" state: "Each element e in K uniquely determines a bijection from M to C, denoted by Ee.Ee is called an encryption function or an encryption transformation." That is, they do impose that encryption requires invertibility. $\endgroup$ – user2891462 Jun 22 at 12:46
  • $\begingroup$ Note that CTR mode doesn't require a PRP it only needs a PRF. $\endgroup$ – kelalaka Jun 22 at 13:59
  • $\begingroup$ In the light of the comment under the question, Rabin's encryption scheme provides a counterexample. So, I'd say encryption is most of the time assumed to be invertible. Though the question could have been worded better. $\endgroup$ – kodlu Jun 22 at 14:19
  • $\begingroup$ One-way encryption is not encryption. Encryption functions are not encryption. Encryption transformations are not encryption. The reason you have to put these adjectives in front of encryption is because these things are not encryption. When you modify something, it is not always still the thing it was before you modified it. If you show someone a tiny box and ask them which of four things could be in it, they would be correct not to choose "car" as one of the options even though a toy car or model car could fit in the box. $\endgroup$ – David Schwartz Jun 22 at 21:21
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "The above are all usually randomized as well"; typically, the decryption algorithm is not randomized... $\endgroup$ – poncho Jun 23 at 2:42
  • $\begingroup$ ""Are incorrect encryption schemes useful?" The answer is no" I would disagree with this sweeping statement. There are many encryption schemes that are not perfectly correct. For most applications statistical correctness is perfectly adequate. $\endgroup$ – Maeher Jun 23 at 8:38
  • $\begingroup$ @Maeher Yes, but "statistically correct" and "incorrect" are different. I interpreted the question as asking about "incorrect" schemes, such as "encrypting" via an OWF/hash function. But this is boring, as if one considers this "encryption", one can create perfectly secure encryption schemes which beat Shannon's bound, removing the motivation for computational notions of security entirely. $\endgroup$ – Mark Jun 23 at 17:50
  • $\begingroup$ The scheme in question isn't statistically correct. But neither is it incorrect in the sense that decryption is always impossible. For some messages decryption works, for some it does not. This probably fulfills the definition of approximate correctness from definition 21 in this paper. (The notion goes back to the PhD thesis of Holenstein, but the presentation in the Mahmood's et al. paper is easier.) So at least theoretically encryption schemes with such correctness can be useful. $\endgroup$ – Maeher Jun 23 at 20:28
  • $\begingroup$ @Maeher They can for sure be useful. Within fully homomorphic encryption the CKKS/HEAAN scheme is only "approximately correct", but is nonetheless useful. But unless you want to add a caveat of the precise notion of correctness you use to Shannon's theorem, the default assumption seems to be perfectly correct (or at least statistically). And decryption working in a message dependent way opens up side channel attacks, so is bad in its own right. $\endgroup$ – Mark Jun 23 at 20:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.