Consider the following encryption scheme where the message space is M $=\{0,1\}$

n and there is

a secure pseudorandom permutation F : $\{0,1\}$

n $->\{0,1\}$

n

$$ Gen$(1$n

$)$ choose a uniform string $\backslash$kappa in $\{0,1\}$

n and output it

$$ Enc $(\backslash$kappa $,$ msg$)$: On input $\backslash$kappa in $\{0,1\}$

n and a message m in $\{0,1\}$

n

$,$ select a random string

r in $\{0,1\}$

n and compute

$1.$ c$1$ :$=$ F$\backslash$kappa $($r$)$

$2.$ c$2$ :$=$ r $$ F$\backslash$kappa $($m$)$

Output the ciphertext $$c$1,$ c$2$

$$ Dec$(\backslash$kappa $,$c$1,$ c$2)$: on input a ciphertext c$1,$ c$2$

m :$=$ F

$1$

$\backslash$kappa

$($F

$1$

$\backslash$kappa

$($c$1)$ c$2)$

$5.(20$ pt$.)$ Show that this scheme is not CCA$-$secure$,$ i$.$e$.,$ there exists a polynomial$-$time

adversary Acca that can always win EXPIND$$CCA

Acca,S

$($n$),$ that is Prh

EXPIND$$CCA

Acca,S

$($n$)=1$i

$=1$

against the encryption scheme. You need to precisely define ALL the steps the adversary

will take, i$.$e$.,$ what messages it selects as challenges in the experiment, and what queries it

makes to the oracles.

Hint: $1)$ you cannot query the decryption oracle with the challenge ciphertext in the experiment, but you can

use a variant of the ciphertext in a query, and $2)$ you might need to make repeated use of the available oracles