Q$1$: Let G:$\{0,1\}^$n$->\{0,1\}^$n is a PRG$.$ We define H$\_$k $($x$)=$G$($k$)$x$,$ is H$\_$k a PRF$?$ If yes, explain why; if not, give an explicit attack $($a PPT adversary that violates the definition$).(10$ pts$)$

Q$2$: Given a PRF E:K$\backslash$times $\{0,1\}^$n$->\{0,1\}^$m$,$ we construct F:K$\backslash$times $\{0,1\}^($n$-1)->\{0,1\}^2$m as follows:

F$($K$,$x$)$:$=$E$($K$,$x$||0)||$E$($K$,$x$||1).$

Is F$($K$,)$ still a PRF$?$ If yes, give a brief proof, if not, give a brief attack showing the violation of PRF definition. $(10$ pts$)$

Q$3$: Can we construct a PRG from a PRF $($assuming the PRF output length is larger than the key length or the input length$)?$ If yes, give the concrete construction and briefly explain; if not, explain why. $(10$ pts$)$

Symmetric key encryption: Suppose $($KeyGen$,$ Enc, Dec$)$ is an IND$-$CPA secure symmetric key encryption. We define the following new encryption algorithms, are the new schemes still IND$-$CPA secure$?$ Briefly explain why. If you believe it is insecure, provide an explicit attacker violating the IND$-$CPA definition.

Q$4$: Enc$\_1($k$,$m$)$ is defined as follows:

$-$It runs Enc$($k$,$m$)$ and obtains c$\_0$;

$-$ It runs Enc$($k$,$m$)$ again to obtain c$\_1.$ The final ciphertext will be $($c$\_0,$c$\_1).(10$ pts$)$

Q$5$: Enc$\_2($k$,$m$)$ is defined as follows:

$-$It runs Enc$($k$,$m$)$ and obtains c$\_0$;

$-$It runs f on m to obtain c$\_1,$ where f is a pseudorandom generator. The final ciphertext will be $($c$\_0,$c$\_1).(10$ pts$)$

Message Authentication Codes.

Suppose $\backslash$Pi $\_1$:$=($KeyGen$\_1,$Tag$\_1,$Verify$\_1)$ and $\backslash$Pi $\_2$:$=($KeyGen$\_2,$Tag$\_2,$Verify$\_2)$ are two message authentication code schemes.

Q$6$: $\backslash$Pi $\_3$:$=($KeyGen$\_3,$Tag$\_3,$Verify$\_3)$ is defined as follows:

$$KeyGen$\_3$ first runs $$KeyGen$\_1$ obtains k$\_1,$ and then runs $$KeyGen$\_2$ obtains k$\_2,$ the output key is $($k$\_1,$ k$\_2).$

$$Tag$\_3[($k$\_1,$ k$\_2),($m$\_1,$ m$\_2)]$ first runs $$Tag$\_1($k$\_1,$ m$\_1)$ and obtains $\backslash$sigma $\_1$ and it runs $$Tag$\_2($k$\_2,$ m$\_1$m$\_2)$ and obtains $\backslash$sigma $\_2,$ where the message m that $$Tag$\_3$ works on is a pair of messages m$\_1,$ m$\_2.$ The final tag is $\backslash$sigma $\_3\backslash$sigma $\_1||\backslash$sigma $\_2.$ The verification can be defined accordingly.

Is $\backslash$Pi $\_3$ a secure MAC? Briefly explain why. $(10$ pts$)$

Q$7$: $\backslash$Pi $\_4$:$=($KeyGen$\_4,$Tag$\_4,$Verify$\_4)$ is defined as follows:

$$KeyGen$\_4$ is identical to $$KeyGen$\_1,$ and it outputs a key k$.$

$$Tag$\_4[$k$,($m$\_1,$ m$\_2)]$ first runs $$Tag$\_1($k$,$ m$\_1)$ and obtains $\backslash$sigma $\_1$ and it runs $$Tag$\_2($k$,$ m$\_2)$ and obtains $\backslash$sigma $\_2.$ The final tag is

$\backslash$sigma $\backslash$sigma $\_1\backslash$sigma $\_2.$

Is $\backslash$Pi $\_4$ a secure MAC? Briefly explain why. $(10$ pts$)$

Q$8$: Given two constructions of message authentication codes $\backslash$Pi $\_1$:$=($KeyGen$\_1,$Tag$\_1,$Verify$\_1),\backslash$Pi $\_2$:$=($KeyGen$\_2,$Tag$\_2,$Verify$\_2).$ Construct a secure MAC scheme $\backslash$Pi $\_3$:$=($KeyGen$\_3,$Tag$\_3,$Dec$\_3)$ which will be secure $($unforgeable$)$ as long as one of $\backslash$Pi $\_1,\backslash$Pi $\_2$ is unforgeable $($but you don$$t know which one$),$ and briefly explain why. $(15$ pts$)$

Q$9$: Explain why the following paradigm does not provide secure authenticated encryption, i$.$e$.$ an encryption scheme that satisfies both IND$-$CPA security and ciphertext integrity $($where the adversary cannot create new ciphertexts without knowing the key or asking the encryption oracle$).$ The paradigm$$s encryption algorithm initially executes an Enc algorithm on message m to obtain c$,$ then runs a Tag algorithm on message m and obtains $\backslash$sigma $.$ The final ciphertext will be $($c$,\backslash$sigma $).(15$ pts$)$