3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ @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. $\endgroup$
    – Blanco
    Commented Mar 21, 2018 at 12:49
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 21, 2018 at 13:10
  • $\begingroup$ @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. $\endgroup$
    – Blanco
    Commented Mar 21, 2018 at 13:19
  • 2
    $\begingroup$ 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... $\endgroup$
    – Geoffroy Couteau
    Commented Mar 21, 2018 at 14:54

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Wasn't OP's question about increasing the size of the ciphertext, without changing the size of the plaintext? (which, admittedly, is a less interesting question) $\endgroup$
    – Geoffroy Couteau
    Commented Mar 21, 2018 at 14:51
  • $\begingroup$ I didn't fully understand the question, I admit. But this is closely related. $\endgroup$
    – Yehuda Lindell
    Commented Mar 21, 2018 at 15:23
  • $\begingroup$ 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. $\endgroup$
    – Blanco
    Commented Mar 23, 2018 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.