If we composed (as in function composition) multiple CPA-secure encryption schemes would the result also be CPA-secure?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Related question: Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure (same OP) $\endgroup$– CodesInChaosCommented May 19, 2015 at 9:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$– ponchoCommented 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$ Commented 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$ Commented May 18, 2015 at 10:12
-
$\begingroup$ "gave that ... distinguishing (either $E$ ... function)" is not how CPA works. $\;$ $\endgroup$– user991Commented May 21, 2015 at 5:37