# Is there a way to double the size of ciphertexts of a public-key scheme which is IND-CCA2

Let $\Pi = \left( \mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec} \right)$ a public-key scheme which is secure in the sense of IND-CCA2. Assume the ciphertexts space is $\mathcal{C} \subset \{0,1\}^{n}$. Can we construct a $\Pi' = \left( \mathrm{Gen}', \mathrm{Enc}', \mathrm{Dec}' \right)$ which is also secure in the sense of IND-CCA2 such that $$\mathcal{C}' \subset \{0,1\}^{2n}$$ and for every plaintext $x$, $$|C'(x)|/|C(x)| > poly(n)$$ and $$0^{n} \Vert \mathrm{Enc}_{pk}(x) \in C'(x)$$ where $C(x) = \{ y \mid y = \mathrm{Enc}_{pk}(x) \}$.

In general, it seems easy to make the ciphertexts longer keeping the level of security. But if I just modify the form of ciphertexts simply (e.g. $r \Vert \mathrm{Enc}_{pk}(x)$ for $r \leftarrow \{ 0,1 \}^{n}$). It can not be secure in the sense of IND-CCA2 any more.

• @user94293 If the form of the ciphertexts is $r \Vert \mathrm{Enc}_{pk}(x)$, then it can not be non-malleability. When you get a ciphertext $r_{1} \Vert y$, you can find another ciphertext $r_{2} \Vert y$ and their plaintexts are the same. And IND-CCA2 $\Leftrightarrow$ NM-CCA2. Actually, I just want to know how to extend the ciphertexts to make it still non-malleability. Mar 21, 2018 at 12:49
• There is a problem here: the prefix isn't really part of the ciphertext, unless it plays some part during decryption, and you haven't specified that. If it does then the ciphertext may not be indistinguishable from random in the given domain. Mar 21, 2018 at 13:10
• @MaartenBodewes I assume that $\mathcal{C}$ embed $\mathcal{C}'$, then I choose a simple function $f \colon y \to 0^{n} \Vert y$. And the prefix may be useless for a part of ciphertexts instead of all the ciphertexts. Mar 21, 2018 at 13:19
• I also see no problem with defining $\mathsf{Enc}'(x)$ as $0^n||\mathsf{Enc}(x)$ for every $x$. We do not care whether the fixed prefix $0^n$ is not used in the decryption, nor do we care about the fact that the ciphertext is not random-looking - none of that prevents this "new" encryption scheme from being IND-CCA2... Mar 21, 2018 at 14:54

• Thanks, this answer may be helpful. According to your answer, I can construct a PKE scheme $\Pi''$ such that $|x''| = 2|x|$, where $x'' \in \mathcal{P}''$ and $x \in \mathcal{P}$. And I can define $\mathrm{Enc}'_{pk'}\left( x' \right) = \mathrm{Enc}''_{pk''}(x_{0} \Vert x')$, where $x_{0} \leftarrow \mathcal{P}$. But I am not sure $\Pi'$ is IND-CCA2 even if $\Pi$ and $\Pi''$ are both IND-CCA2. Mar 23, 2018 at 2:55