We have discussed CPA security in class. This question is testing your understanding of CPA

security.

$(30$ pt$.)$ Consider the following encryption scheme $S=($Gen$,$ Enc, Dec$)$ where $F$ is a pseudo$-$

random permutation $($PRP$).$ Recall that a PRP is a bijective PRF and a PRP is invertible

Gen $(1^n)$ choose a uniform string $in\{0,1{\}}^n$ for $F$ and output it

Enc $(,msg)$ : On input $in\{0,1{\}}^n$ and a message msgin$\{0,1{\}}^n,$ select a random string

rin$\{0,1{\}}^n$ output the ciphertext

$ct$:$=$

Dec$(,ct)$ : on input ciphertext $c=($:$r,s$:$),$ output

$msg$:$=F_{}^{-1}(so+r)$

$($a$)(5$ pt$.)$ Is this a CPA secure encryption scheme? Explain your answer

$($b$)(25$ pt$.)$ Consider that the encryption function is now modified to

$ct$:$=$

Write down the decryption function for this ciphertext, and prove that this encryption

scheme is CPA$-$secure$.$ You need to use the reduction proof technique discussed in class,

and compute the probability bound for any PPT$.$ adversary in $Ex{P}_{A_{\text{c}\text{p}\text{a}},S^{\text{'}}}^{\text{I}\text{N}\text{D}-\text{C}\text{P}\text{A}}(n)$ for the

modified encryption scheme $S^{\text{'}}.$ Please refer to the slides to see how you justify each

step of the reduction.