2
$\begingroup$

$E_1$ and $E_2$ are IND-CPA secure encryption schemes. $E$ is defined as: $k_1,k_2 \leftarrow K_1 \times K_2$ . $E_{k_1,k_2}(m) \leftarrow E_{1,k_1}(m)||E_{2,k_2}(m)$.

Hope the notations are in an obvious manner. $\leftarrow$ means randomly choosing an element from the corresponding distribution. || stands for concatenation.

My question is whether the encryption scheme $E$ is IND-CPA secure.

Intuitively, this would be secure. If you can not get any information from either $E_1$ or $E_2$, should you get no information given both. (Of course there is a loophole here: $E_1$ or $E_2$ by itself may not leak information, however the combination of them may give some information away.)

When I tried to prove it I can not reduce the break of $E$ to either $E_1$ or $E_2$. Neither can I find a counter example.

Improve this question
$\endgroup$
2
  • $\begingroup$ if E1 and E2 are both IND-CPA then that combination should also be IND-CPA $\endgroup$
    – user1028028
    Apr 1 '14 at 7:13
  • 1
    $\begingroup$ You should emphasize that independent keys are used. That is an important detail. $\endgroup$
    – ArekBulski
    Mar 10 '16 at 7:50
6
$\begingroup$

Yes, $E$ will be always be secure. This follows from a standard type of proof called a hybrid argument. Giving the full details would be tedious, so here is a sketch in case you are familiar with hybrid arguments:

We define games $H_0,H_1,H_2$. We let $H_0$ be the IND-CPA game, but with the game's secret bit hardcoded to $0$. So the game always outputs $E_{1,k_1}(m_0)\|E_{2,k_2}(m_0)$ when the adversary submits $(m_0,m_1)$ as its challenge.

Next define $H_1$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_0)$ always, and finally $H_2$ to always return $E_{1,k_1}(m_1)\|E_{2,k_2}(m_1)$.

A successful IND-CPA adversary $\mathcal{A}$ against $E$ is one that distinguishes $H_0$ and $H_2$. The games $H_0,H_1,H_2$ are chosen so that we can use $\mathcal{A}$ to build adversaries $\mathcal{A}_0, \mathcal{A}_1$ to distinguish between $H_0$ and $H_1$ or between $H_1$ and $H_2$. But this will mean that at least one of the adversaries breaks the IND-CPA security of $E_1$ or $E_2$ respectively.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. Hybrid argument seems to be a promising tool. But I have some confusion about your argument. It seems that the argument does not use the restrictions that $E_1$ and $E_2$ are different schemes (as my question does not require such restriction), and the keys for both encryption schemes are independent. So I assume the same argument will work for same encryption schemes and/or identical encryption key. But then a counterexample is the correlated one time pads. $E_{1,k}(m)=m+k$ and $E_{2,k}(m)=m-k$. Though one time pad is not IND-CPA, I think it suffices to demonstrate. $\endgroup$
    – qbyte
    Apr 2 '14 at 5:11
  • $\begingroup$ Generally speaking, an adversary who distinguishes between $H_0$ and $H_1$ can break $E_1$ (the assertion from your argument), in my opinion, implies the claim that for distributions $X,Y,Z$, if $X||Y$ and $X||Z$ are distinguishable then $Y$ and $Z$ are distinguishable. But to my understanding, it is not correct. If $Y$ and $Z$ are indeed indistinguishable, one can set $X=Y+1$ to make $X||Y$ and $X||Z$ distinguishable. $\endgroup$
    – qbyte
    Apr 2 '14 at 5:18
  • $\begingroup$ Recall that the keys are independent. $\;$ $\endgroup$
    – user991
    Apr 2 '14 at 15:03
  • 2
    $\begingroup$ The argument works with different $E_1,E_2$ or $E_1 = E_2$, as long as $k_1$ and $k_2$ are independent. The trick is that the reductions will choose one of the keys itself (depending on which step of the hybrid argument you're doing), and it will let the game choose the other key and use its oracles to simulate the hybrid. $\endgroup$
    – David Cash
    Apr 2 '14 at 17:40

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.