1
$\begingroup$

Katz and Lindell book claim that from the theorem:

  1. Any private-key encryption scheme that is CPA-secure is also CPA-secure for multiple encryptions.

Follows the fact that:

  1. If $(Gen,Enc,Dec)$ is a fixed-length ($M_n = \{0,1\}^n$) CPA-secure ES then $(Gen,Enc',Dec')$ with $M_n' = (\{0,1\}^n)^{*}$ and $Enc_k'(m) = Enc_k(m^{(1)})||\ldots||Enc_k(m^{(s)})$ is also CPA-secure.

Why is it the case?

What strikes me more is that a similar theorem to 1. holds for CCA-security:

  1. Any private-key encryption scheme that is CCA-secure is also CCA-secure for multiple encryptions.

However, the construction does not hold (according to my slides) in the later case:

  1. Assuming $(Gen,Enc,Dec)$ is CCA-secure with $M_n = \{0,1\}^n$ then one can show that $(Gen,Enc',Dec')$ is not CCA-secure.
$\endgroup$
  • $\begingroup$ Doesn't CCA fail with multiple encryptions? $\endgroup$ – kelalaka Nov 18 '18 at 22:38
  • $\begingroup$ @kelalaka from what I understand you mean that you know how to proof statement 4. i've tried some malleability argument but it didn't work out $\endgroup$ – Rodrigo Nov 18 '18 at 22:47
  • $\begingroup$ See proposition 3.20 in the second ed. $\endgroup$ – kelalaka Nov 18 '18 at 22:57
  • $\begingroup$ @kelalaka the problem I see is that in that proposition the are assumming that encryption is deterministic (the example taken is the one-time-pad). However, here the encryption does not need to be deterministic $\endgroup$ – Rodrigo Nov 18 '18 at 23:06
  • $\begingroup$ Note: Heavy theory is not really the emphasis of Katz-Lindell. If you want to go there, get Goldreich (draft version are available for free on his homepage). $\endgroup$ – fkraiem Nov 19 '18 at 3:54
5
$\begingroup$

The proof of (1) is not given in the chapter on symmetric encryption since it requires knowing the hybrid proof technique that is taught in Chapter 7. However, the argument is proven in Chapter 11 for the asymmetric case (see Theorem 11.6 and the proof on page 383). Essentially the same proof holds for the symmetric case as well (except that instead of the reduction $\mathcal{A}'$ on page 385 computing the plaintexts itself for $j<i$ and $j>i$ in steps 2(a) and 2(c) respectively, it asks its encryption oracle to do it and uses the responses).

Regarding CCA security, the proof of multiple encryptions indeed does go through as well. However, unlike CPA security, it does not imply that you can concatenate ciphertexts into one ciphertext. That is, you can encrypt multiple messages, but you cannot encrypt longer messages by concatenating. The reason is that if you encrypt a long message by concatenating ciphertexts (and you call this the new ciphertext) then the attacker can drop the last sub-ciphertext and ask for decryption (it is allowed to ask for decryption since this is not the same ciphertext received).

$\endgroup$

Your Answer

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

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