# Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure

I recently started studying cryptography but I am not sure I quite understand the concept of proof by reduction. Question I am trying to solve is as follow:

Suppose $$\Pi$$ is a symmetric encryption scheme which $$C \subseteq M$$ ($$M$$ is message space and $$C$$ is ciphertext space). then we have $$\Pi'$$ with same key generation and decryption algorithm as $$\Pi$$ ($$K' = K , D' = D$$) with encryption algorithm as follow
$$E_k'(m) = E_k(E_k(m)).$$ I am trying to proof or reject:

a ) if $$\Pi$$ is indistinguishable in presence of an eavesdropper (simplest case when attacker can only see a ciphertext) then $$\Pi'$$ is indistinguishable.

b ) if $$\Pi$$ is CPA-secure then $$\Pi'$$ is CPA-scure.

for case a using proof by reduction i came up with solution

$$C \subseteq M$$ implies a bijection between $$M$$ and $$C$$ so whenever $$A'$$ guess the chosen bit correctly $$A$$ will do as well so we have

$$Advantage\: of\: A \geq Advantage\: of\: A'$$

So if $$A'$$ be a attacker with non negligible advantage $$A$$ will be as well so a is true.

Am I using reduction correctly? What bout part b? Can we use almost same reasoning or there is an attacker for this case to prove $$\Pi'$$ is not CPA-secure?

EDIT : regarding @Ievgeni answer for part a one time pad is a counterexample and regarding @Mikero comment i think reduction for part b might be something like below

conclusion :

part a : wrong . and one time pad is an counterexample and first picture is totally wrong.

part b : right . and proof is by reduction(picture two). for this reduction we have

$$Advantage\: of\: A = Advantage\: of\: A'$$

so if advantage of $$A'$$ be non-negligible advantage of $$A$$ will be too.

• In your second diagram, be clear that when the reduction queries “challenge,” it is querying the encryption oracle, not the challenge oracle (which requires two messages, and can only be queried once according to most definitions). Sep 24 '20 at 11:49
• @Chris Peikert beside point you mentioned, do you see other problem with second reduction? I think second reduction(second diagram) solve the part b of question because advantage of attacker $A$ is equal to advantage of $A'$ right? and proof is complete, right? Sep 24 '20 at 12:24
• I think the reduction looks good. You need to analyze it to show that the simulation is perfect and hence the advantages are the same, but that is straightforward. Sep 24 '20 at 12:26

As Mikero noticed, the problem in your first proof is the fact that you can't suppose that $$\mathcal{A}$$ knows the secret $$k$$, and thus it can not encrypt the challenge.

And if you don't encrypt the challenge, then the input is not what is expected by $$A'$$. $$A'$$ is waiting $$Enc^2_k(m)$$ or $$Enc^2_k(m')$$ as a challenge not $$Enc_k(m)$$ or $$Enc_k(m')$$.

When you are doing a game-based proof, an important notion is the notion of indistinguishability. For example If you are using an algorithm $$\mathcal{A}$$ as an oracle. And if you want to use some properties about the output of $$\mathcal{A}$$, it is important to check that the input of $$\mathcal{A}$$ follow the distribution which is mentioned in the property.

In your example, you are giving to the adversary $$Enc(m)$$ and not $$Enc(Enc(m))$$, it's completely different in the general case.

Let consider the xor encryption $$Enc_k(m)= k\oplus m$$.

It's really easy to build an attacker (let say a powerfull attacker who decrypts the ciphertext without the secret key) against $$Enc^2$$, it's just the identity function (Because $$Dec_k^2=Enc^2_k$$ is the identity function for all $$k$$.)

Then even $$Enc$$ is semantically secure, then $$Enc^2$$ could not to be. So a) is false.

But your proof about (b) seems correct to me.

• why not ? challenge is $E_k(m)$ or $E_k(m')$ so $A'$ gets $E_k(E_k(m))$ or $E_k(E_k(m'))$ as input. whats is wrong with this ? Sep 23 '20 at 9:20
• Suppose $E$ is a xor ($E_k(m)= m \oplus k$), then is you choose $m$, $\Pi$ will follow an uniform distribution, and $\Pi'$ will follow a constant distribution $m\oplus k \oplus k=m$. Sep 23 '20 at 9:26
• so one time pad is a counterexample for part a, what about part b? does this reduction work for part b? Sep 23 '20 at 12:21
• No, when you do a reduction, you have to prove that the distribution is similar, in both game (the real and the one you built to solve your proper problem). Think about the xor to reinforce your intuition. Sep 23 '20 at 13:21
• @alfred: Look at your picture. You wrote it so that adversary A needs to use the value $k$. How does it know what $k$ is? Sep 23 '20 at 15:11

If you use the same key $$k$$, as in the definition, then the answer is: You are trying to prove something that is false.

If we use the one time pad as symmetric cipher, then we get:

$$E'_k(m) = E_k(E_k(m))= m \oplus k \oplus k=m$$

It should be fairly obvious, that that doesn't give any security at all.

• thank for answer, but part a of question was already solved . what is your idea about part b ? Sep 23 '20 at 16:56
• With decryption oracles, one-time-pad is just a Vigenere. So it's not secure neither. Sep 25 '20 at 9:45
• Chosen-plaintext security typically means semantic security, which is: distinguishing encryption of m0 and m1 chosen by the attacker using the encryption oracle any amount of times within the time limit. One-time pad is not semantically secure. And does not satisfy the notion in a) as well. Oct 1 '20 at 7:22