5
$\begingroup$

Any thoughts on how this can be done?

Let $\Pi_1 = (\mathrm{Gen}_1, \mathrm{Enc}_1, \mathrm{Dec}_1)$ and $\Pi_2 = (\mathrm{Gen}_2, \mathrm{Enc}_2, \mathrm{Dec}_2)$ be two encryption schemes for which it is known that at least one is CPA-secure. The problem is that you don't know which one is CPA-secure and which one may not be. Show how to construct an encryption scheme $\Pi$ that is guaranteed to be CPA-secure as long as at least one of $\Pi_1$ or $\Pi_2$ is CPA-secure.

Problem 3.21 - Jonathan Katz, Yehuda Lindell - Introduction to Modern Cryptography: Principles and Protocols.

Improve this question
$\endgroup$
1
10
$\begingroup$

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt.

If $\mathrm{Gen}_1$ and $\mathrm{Gen}_2$ are two random generators then you may want to XOR those together as well when generating $s_1$. I presume however that they are used to generate the secret keys.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ While this certainly is valid, and matches the hint given in the question before it vanished, I do not see anything wrong with cascaded encryption (using independent keys), which does not depend on a random generator, and has shorter ciphertext. $\endgroup$ – fgrieu♦ May 19 '15 at 6:52
  • 1
    $\begingroup$ Ok all seems well now. @fgrieu I would happily upvote another answer. This one is indeed more complex than strictly necessary. $\endgroup$ – Maarten Bodewes♦ May 19 '15 at 9:38
  • 3
    $\begingroup$ @fgrieu : $\:$ The inner scheme could be such that the lengths of its ciphertexts noticeably depend on their corresponding plaintexts, and the outer scheme could be CPA-secure but still such that its ciphertexts reveal enough about the lengths of their corresponding plaintexts. $\;\;\;\;$ $\endgroup$ – user991 May 19 '15 at 23:22
  • 2
    $\begingroup$ @MaartenBodewes : $\:$ You're missing the point: In the case I described, the cascade $\hspace{1.13 in}$ would not be CPA-secure, even though one of the schemes would be CPA-secure. $\hspace{1.39 in}$ $\endgroup$ – user991 May 20 '15 at 1:07
  • 3
    $\begingroup$ @Ricky Demer: indeed if the first and non-CPA-secure encryption scheme causes an expansion of 1000 bytes for plaintext that starts with the string "fubar", cascaded encryption is insecure, but the answer gives a CPA-secure scheme. Good catch; I will remember considering leaks by size in questions on cascaded encryption. $\endgroup$ – fgrieu♦ May 20 '15 at 5:30

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.