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

2018-03-21 15:44:32

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)| > ploy(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.

This is actually a very interesting theoretical question that was open for many years. For CPA-secure encryption, it is possible to simply concatenate ciphertexts in o

  • This is actually a very interesting theoretical question that was open for many years. For CPA-secure encryption, it is possible to simply concatenate ciphertexts in order to increase the plaintext space. However, for CCA2, it is not sufficient to concatenate since it's possible to move around the bits and maul the ciphertext. Note that if you assume that the original plaintext space is large (super-polynomial), then it's easy to solve by just using hybrid encryption. This is because you can encrypt a symmetric key and work from there. However, if the plaintext space is small -- especially hard if a single bit -- then it's very unclear. Fortunately, Myers and shelat solved this in FOCS 2009 in a paper entitled Bit encryption is complete.

    2018-03-21 18:14:04