1
$\begingroup$

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 my reduction

$ 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 reduction parrt b

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ Sep 24 '20 at 11:49
  • $\begingroup$ @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? $\endgroup$
    – alfred
    Sep 24 '20 at 12:24
  • $\begingroup$ 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. $\endgroup$ Sep 24 '20 at 12:26
0
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – alfred
    Sep 23 '20 at 9:20
  • $\begingroup$ 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$. $\endgroup$
    – Ievgeni
    Sep 23 '20 at 9:26
  • $\begingroup$ so one time pad is a counterexample for part a, what about part b? does this reduction work for part b? $\endgroup$
    – alfred
    Sep 23 '20 at 12:21
  • $\begingroup$ 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. $\endgroup$
    – Ievgeni
    Sep 23 '20 at 13:21
  • 1
    $\begingroup$ @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? $\endgroup$
    – Mikero
    Sep 23 '20 at 15:11
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ thank for answer, but part a of question was already solved . what is your idea about part b ? $\endgroup$
    – alfred
    Sep 23 '20 at 16:56
  • $\begingroup$ With decryption oracles, one-time-pad is just a Vigenere. So it's not secure neither. $\endgroup$
    – Ievgeni
    Sep 25 '20 at 9:45
  • $\begingroup$ 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. $\endgroup$
    – Fractalice
    Oct 1 '20 at 7:22

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.