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[0] \Vert m[1] \Vert \cdots \Vert m[n] \in \{\, 0,1 \,\}^{n} \subseteq \mathcal{M}'$, $$\mathrm{Enc}'_{pk}(m) = (\mathrm{Enc}_{pk}(m[0]), \mathrm{Enc}_{pk}(m[1]), \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.)

  • $\begingroup$ 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? $\endgroup$ – Maarten Bodewes Nov 17 '19 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes Nov 17 '19 at 16:02
  • $\begingroup$ @ 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. $\endgroup$ – Blanco Nov 18 '19 at 4:57

Your Answer

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

Browse other questions tagged or ask your own question.