# Is bit encryption enough?

Assume that $$\Pi$$ is a secure PKE scheme (or other appropriate encryption schemes) with 1-bit message space. And it can be applied bit-by-bit to construct a many-bit encryption scheme $$\Pi'$$.

Actually, let $$\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$$ with $$\mathcal{M} = \{\, 0,1 \,\}$$. And we define $$\Pi' = (\mathrm{Gen}', \mathrm{Enc}', \mathrm{Dec}')$$ with $$\mathcal{M}' = \{\, 0,1 \,\}^{*}$$ or $$\mathcal{M}' = \{\, 0,1 \,\}^{\mathrm{poly}(\lambda)}$$ such that $$\mathrm{Gen}' = \mathrm{Gen}$$ and for every $$m = m \Vert m \Vert \cdots \Vert m[n] \in \{\, 0,1 \,\}^{n} \subseteq \mathcal{M}'$$, $$\mathrm{Enc}'_{pk}(m) = (\mathrm{Enc}_{pk}(m), \mathrm{Enc}_{pk}(m), \ldots, \mathrm{Enc}_{pk}(m[n]))$$ for every $$\mathrm{\mathbf{c}} = (c_{0}, c_{1}, \ldots, c_{n}) \in \mathcal{C}^{n} \subseteq \mathcal{C}'$$, $$\mathrm{Dec}'_{sk}(\mathrm{\mathbf{c}}) = \mathrm{Dec}_{sk}(c_{0}) \Vert \mathrm{Dec}_{sk}(c_{1}) \Vert \cdots \Vert \mathrm{Dec}_{sk}(c_{n})$$

Can we regard these two schemes as a same scheme in some sense? In other words, is $$\Pi'$$ as "good" as $$\Pi$$ in some sense? I want a comprehensive assessment.

As for the security, I know some conclusions.

1. $$\Pi$$ is IND-CPA (IND-CCA1) secure iff $$\Pi'$$ is IND-CPA (IND-CCA1) secure. Although $$\Pi'$$ is not IND-CCA2 security.

2. We can construct an IND-CCA2 PKE scheme by using $$\Pi$$ if $$\Pi$$ is IND-CCA2. (Bit encryption is complete).

As for the effectiveness, it seems that $$\Pi'$$ is always inefficient.

Is that all the motivation to construct a new PKE scheme with large message space? (Even the messages have different algebraic structures.)

• You're pointing to an entire paper, could you possibly include the title of the paper in the question and point out the right section? Could you possibly make the title a bit more specific, e.g. show that you are talking about a PKE scheme and security notions? – Maarten Bodewes Nov 17 '19 at 16:00
• Just a thought: if you'd use RSA-OAEP and only let it accept single bits then wouldn't that be an example of a scheme $\Pi$ and wouldn't it clearly show that you can use it to build $\Pi'$ (by using simple concatenation)? It would also show that it is wildly inefficient of course. – Maarten Bodewes Nov 17 '19 at 16:02
• @ Maarten Bodewes, I think I need a multifaceted perspective (not only the security notions) about whether it is necessary to construct a new PKE scheme with large message space. And $\Pi$ is a secure 1-bit encryption scheme is a premise of my question. – Blanco Nov 18 '19 at 4:57