Relationship between the (provable) security and the size of the plaintext space

Question

Motivation: An encryption scheme is used to encrypt the message which belongs to the plaintext space. The scheme designer does not know what kinds of message is valid (i.e. what the plaintext space is). So I believe that the (provable) security does not depend on the size of the plaintext space. However there are some facts that do not support my view.

For example, we consider IND-CPA/IND-CCA1/IND-CCA2 of the public-key ecnryption scheme.

Let $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ be a PKE scheme and let $A = (A_{1}, A_{2})$ be an adversary. For $\mathrm{atk} \in \{\, \mathrm{cpa}, \mathrm{cca1}, \mathrm{cca2} \,\}$ and $k \in \mathbb{N}$, let $$\mathrm{Adv}_{\Pi, A}^{\text{ind-atk}}(k) = \Pr\left[ \mathrm{Exp}_{\Pi, A}^{\text{ind-atk-}1}(k) = 1 \right] - \Pr\left[ \mathrm{Exp}_{\Pi, A}^{\text{ind-atk-}0}(k) = 0 \right] $$ where, for $b, d \in \{\, 0,1 \,\}$, $$\Pr\left[ \mathrm{Exp}_{\Pi, A}^{\text{ind-atk-}b}(k) = d \right] = \Pr\left[ \begin{gathered} (pk,sk) \leftarrow \mathrm{Gen}(1^{k}) \\ (x_{0}, x_{1}, s) \leftarrow A_{1}^{O_{1}(\cdot)}(pk)\text{ s.t. } |x_{0}| = |x_{1}| \\ y \leftarrow \mathrm{Enc}_{pk}(x_{b}) \\ A_{2}^{O_{2}(\cdot)}(x_{0}, x_{1}, s, y) = d\\ \end{gathered} \right]$$ and $$ \begin{aligned} &\text{if } \mathrm{atk} = \mathrm{cpa} &&\text{then} &&O_{1}(\cdot) = \varepsilon && O_{2}(\cdot) = \varepsilon \\ &\text{if } \mathrm{atk} = \mathrm{cca1} &&\text{then} &&O_{1}(\cdot) = \mathrm{Dec}_{sk}(\cdot) && O_{2}(\cdot) = \varepsilon \\ &\text{if } \mathrm{atk} = \mathrm{cca2} &&\text{then} &&O_{1}(\cdot) = \mathrm{Dec}_{sk}(\cdot) && O_{2}(\cdot) = \mathrm{Dec}_{sk}(\cdot) \\ \end{aligned} $$ Above it is mandated that $|x_0| = |x_1|$. In the case of CCA2, we further insist that $A_2$ does not ask its oracle to decrypt $y$. We say that $\Pi$ is secure in the sense of IND-ATK if $A$ being polynomial-time implies that $\mathrm{Adv}^{\text{ind-atk}}_{\Pi, A}( \cdot)$ is negligible.

There is no limitation of the plaintext space in the definition. As I know, there are 3 classes of plaintext space:

1. The plaintext space is finite (the message has the fixed length), $\mathcal{P} = \{\, 0,1 \,\}^{l}$.

2. The plaintext space is infinite, $\mathcal{P} = \{\, 0,1 \,\}^{*}$.

3. The size of the plaintext space depends on the security parameter, $|\mathcal{P}| = f(k)$ (e.g. $\mathcal{P} = \{\, 0,1 \,\}^{k}$)

So, I have the following problems:

Q1. As the definition says, is it assumed that $|\mathcal{P}| = \{\, 0,1 \,\}^{*}$? Or should it be mandated that $|x_0| = |x_1|$ and $x_0, x_1 \in \mathcal{P}$(whatever $\mathcal{P}$ is) in the definition? Formally, $$\Pr\left[ \mathrm{Exp}_{\Pi, A}^{\text{ind-atk-}b}(k) = d \right] = \Pr\left[ \begin{gathered} (pk,sk) \leftarrow \mathrm{Gen}(1^{k}) \\ (x_{0}, x_{1}, s) \leftarrow A_{1}^{O_{1}(\cdot)}(pk)\text{ s.t. } |x_{0}| = |x_{1}|, x_{0}, x_{1} \in \mathcal{P} \\ y \leftarrow \mathrm{Enc}_{pk}(x_{b}) \\ A_{2}^{O_{2}(\cdot)}(x_{0}, x_{1}, s, y) = d\\ \end{gathered} \right]$$

Q2. If the security of a scheme does not depends on $|\mathcal{P}|$. Should I say that we always regard $\mathcal{P}$ as $\{\, 0,1 \,\}$ without loss of generality? (If $\Pi$ is secure in the sense of IND-ATK, it is seems that $\Pi$ is also secure in the sense of IND-ATK with a smaller plaintext space.) If it is true, we can simplify the equation $$\Pr\left[ \mathrm{Exp}_{\Pi, A}^{\text{ind-atk-}b}(k) = d \right] = \left[ \begin{gathered} (pk,sk) \leftarrow \mathrm{Gen}(1^{k}) \\ s \leftarrow A_{1}^{O_{1}(\cdot)}(pk) \\ y \leftarrow \mathrm{Enc}_{pk}(b) \\ A_{2}^{O_{2}(\cdot)}(s, y) = d\\ \end{gathered} \right]$$

Q3. If the security of a scheme depends on $\mathcal{P}$. Does there exist the following situation: $A,B$ are two notions of security, $A$ is stronger than $B$ if the plaintext space is large and $A$ is equivalence to $B$ if the plaintext space is small. Is it meaningful to consider the relation between two notions of security on the condition of different plaintext spaces?

Q4. Whether there is a specific scheme such that $\mathcal{P} = \{\, 0,1 \,\}^*$? Whether there is a scheme which is secure in the sense of IND-ATK with $\mathcal{P} = \{\, 0,1 \,\}^{l}$, can we construct a scheme which is secure in the sense of IND-ATK with $\mathcal{P} = \{\, 0,1 \,\}^{*}$ by blockwise encryption?

Answer 1

A1. Yes, formally it needs to be enforced that the messages are from the message space of the encryption scheme in question. Otherwise the experiment is not well defined. This is often ignored and it is just implicitly assumed that the adversary will output valid messages.

A2. Assuming a message space of $\{0,1\}$ is definitely not without loss of generality. First of all, $0$ and $1$ are not necessarily even elements of the message space. Second, security for message space $\{0,1\}$ does not imply security for any larger messagespace.

Say I have an Encryption scheme for messages in $\{0,1\}$ that is proven CPA secure. Now I define a new Encryption scheme for $\{0,1\} \cup \{0,1\}^2$ that works as follows: If $m\in\{0,1\}$ encrypt with the original scheme. Otherwise output the plaintext. This scheme can be proven secure if the plaintext space is restricted to $\{0,1\}$ but is clearly insecure for its full plaintext space.

In general, if an encryption scheme is secure for a plaintext space $\mathcal{P}$ then it is also secure for any plaintext space $\mathcal{P}'\subseteq\mathcal{P}$. But for any $\mathcal{P}'\not\subseteq\mathcal{P}$ there is no guarantee whatsoever.

A3. Of course you can come up with this kind of notion. Let's start with the most extreme example where $|\mathcal{P}|=1$. In that case all indistinguishability based notion are equivalent (and trivial, because there cannot exist a $\mathcal{A}$ that outputs $m_0\neq m_1$ with $\{m_0,m_1\}\in\mathcal{P}$. But clearly we know that with larger plaintext spaces CPA and CCA notions are not equivalent.

As a more realistic example consider your notion from Q2. Clearly in the case of $\mathcal{P}=\{0,1\}$ that notion (where you can actually get rid of the first stage of $\mathcal{A}$) is equivalent to the corresponding notion from your original definition. However, as I showed above this equivalence does not hold in general.

A4. At least in theory an encryption scheme implemented by a block-cipher in an appropriate mode of operation is CPA (e.g. CBC or CTR mode) or CCA (e.g. GCM mode) secure and has message space $\{0,1\}^*$.

Whether encrypting blockwise is secure depends on the security notion. For CPA and CCA1 security you can prove that security is preserved if you encrypt blockwise. The proof works with a standard hybrid argument.

For CCA2 security this is not the case. With blockwise encryption, you would receive as a challenge $y$ a list of ciphertexts $c_1,\dots, c_\ell$. The adversary could simply drop one or more of those blocks and query the remaining blocks to the decryption oracle. As this new ciphertext is different from $y$, the oracle would decrypt and thus reveal which message was encrypted.