If we composed (as in function composition) multiple CPA-secure encryption schemes would the result also be CPA-secure?


1 Answer 1


Yes, if (and this is important) the keys for $E$ and $S$ are selected independently.

Consider that we had two encryption methods $E$, $S$ for which their composition $E(S(x))$ is not CPA secure; that is, we have some distinguisher $D$ that had some advantage in distinguishing that from a random function. Then, we can build a distinguisher for $E$ (by selecting a random key for $S$, then then use the distinguisher $D$, and when it made a query, we'd take the plaintext it selected, encrypt it with $S$ with our random key, and then gave that ciphertext to the object we're distinguishing (either $E$ or the random function).

Similar logic can be used to show that we can use the distinguisher to distinguish the inner function (by selecting a random key for the outer function).

Hence, if $E$ and $S$ are indistinguishable, so is their composition (in the CPA model). In fact, we can make a stronger statement; if either are indistinguishable, so is the composition.

On the other hand, if the keys aren't independent, then all bets are off. Not only do these simulation arguments don't work (as the simulator is unable to select the appropriate key), but the possible insecurity of the system can be seen by considering the case where $E$ and $S$ are inverses of each other.

  • $\begingroup$ Yes, we need to assume that the keys are independent; I'll update my answer accordingly $\endgroup$
    – poncho
    May 17, 2015 at 21:17
  • $\begingroup$ You need to make a hybrid argument, yours is wrong because you don't invoke IND-CPA of S and it needs to be. A proof by game is more appropriate I think. $\endgroup$ May 18, 2015 at 10:03
  • $\begingroup$ I'm wrong - If any of them is IND-CPA then it should be ok as long as keys are independant $\endgroup$ May 18, 2015 at 10:12
  • $\begingroup$ "gave that ... distinguishing (either $E$ ... function)" is not how CPA works. $\;$ $\endgroup$
    – user991
    May 21, 2015 at 5:37

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.