In a cryptosystem, why does the message space need to be finite?

Question

I am learning cryptography through Douglas Stinson's book: Cryptography -- Theory and Practice (3rd ed.). The first definition in the text is

A cryptosystem is a five tuple (M,C,K,E,D) where 
 - M is a finite set ...

That is the set of "plaintexts" or unencrypted messages must be finite. My question is: how reasonable of a definition is this? For any natural language, there are an infinite number of messages that one can send. It seems this is incomplete to me. It seems that M is the alphabet we are encrypting, and to encrypt a string in M* (what I would call the message space) we encrypt by $$e_k(m_1 \cdots m_j) = e_k(m_1) \cdots e_k(m_j)$$ (where $e_k \in E$ is an encryption function -- note that elements of $E$ can be viewed as functions $e : K \to M \to C$). But I feel this is a bad idea because we are reusing a key.

Answer 1

One reason for this is that one can first define a cryptosystem having a small finite message space, and then on top of that, construct another cryptosystem that can handle longer message spaces. This is a very reasonable modular design methodology.

A couple of examples:

• given a block cipher with a finite message space, one can use a block cipher mode (like CBC or CTR) to extend the message space to be essentially infinite.

• given the Paillier public-key cryptosystem, one can institute a specific length-parameter (as done by Damgård and Jurik) and allow to efficiency encrypt messages of arbitrary length.

One caveat though is that if messages are of arbitrary length, then also the time to encrypt increases accordingly. If we want to be the cryptosystem to be secure against adversaries working in some time $t$, it is better to restrict the message length so that encrypting any messages of that length takes considerably less time than breaking the cryptosystem (with a small message length).

Remark: one can obviously try to define security in a way that breaking small messages can be easier than breaking long messages, but this does not make sense in practice.

Answer 2

We, of course, want our message space, $\mathcal{M}$, to be able to include messages of arbitrary size. I am not familiar with the details of Stinson's definition of a cryptosystem, but I would not be surprised if it is set up to be scaleable, iterable, or chainable using other constructions. Your concern is warranted, but there are a couple of things to keep in mind:

• Suppose that $\mathcal{M}$ is countably infinite so that we can get the most out of it. But, we also want our $\text{Enc}_k$ and $\text{Dec}_k$ to be efficiently computable by Alice and Bob. If Alice wants to send Bob the message, "ATTACKATDAWN", then would would be insane for our $\text{Enc}_k$ function to produce a ciphertext of $(6\times10^{22})!$ bits. In practice, Bob would probably have died by the time he received it and most certainly will not have by dawn. This is not feasible by practical standards, but it would not be feasible by theoretical standards either (Space and Time Complexity).
• If we, as a result, do enforce a limit on how large the ciphertext of any message of length, $n$, gets, we are not going to get that full use out of that countably infinite $\mathcal{M}$. Your adversary is going to get $\left|c\right|$ from $c$, anyways, giving them some information about the length of the plaintext. Instead of varying the length of the resulting ciphertext, we might use our computational resources better by just increasing the key length. Our primary goal is to balance resource efficiency with security.
• Many of the definitions, constructions, and proofs in cryptography specifically use a scalable, but finite $\mathcal{M}$. Example: probability measures. When defining or using something akin to $\mathbb{P}[M=m\mid C=c]$, using a countably infinite, $\mathcal{M}$, may not be appropriate. Instead, we might suppose an arbitrary length, $k$, ahead of time ($\left| \mathcal{M}\right |=2^k$) and prove our theorems using that.

The block cipher that you present is, as you mention, not secure for the reason that you mentioned. The proper way of getting around this is to use round keys. That is, the key for each successive block is determined by the previous key and message. Wikipedia's article on Block Ciphers provides sufficient details for this.

Answer 3

You asked if this definition is reasonable. Yes, this is reasonable.

It's not that the message space needs to be finite. However, it's reasonable to restrict the message space to be finite. This restriction is not a big deal. In practice, limiting the message space to a finite set (e.g., by insisting that messages can be at most $2^{64}$ bits long) is not a serious restriction.

Conceptually, for many cryptosystems, the message space could be infinite: it could be $\{0,1\}^*$, or it could be the set of all bit-strings whose length is a multiple of 128. Those are infinite sets. However, once we get around to proving a security theorem, we typically need to impose a restriction on the maximum length anyway, to enable us to prove certain security bounds.

So, from a practical perspective, there's no real harm done in defining a cryptosystem this way. If you don't like it, you could equally as well consider an alternative definition where the message space was infinite (e.g., a subset of $\{0,1\}^*$), but I'm not sure that you gain anything important from that.

---

Also, it's useful to understand that standard encryption schemes do not hide the length of the message. Therefore, when defining the security of a cryptosystem, our theorems often essentially restrict consideration to a set of messages of fixed length (all possible messages have the same length) and show that the cryptosystem does not give the attacker any clue which of them were sent. So, in some sense, when we go to prove our security theorem, we are effectively forced to work with a finite message space, due to the fact that the length is fixed and known to the attacker. This is fundamental: it's not realistically possible to build a cryptosystem that prevents the attacker from learning something about the length of the message.