Q$1$: Let G:$0,1$n$0,1$n is a PRG$.$ We define Hkx$=$Gk$$x$,$ is Hk a PRF$?$ If yes, explain why; if not, give an explicit attack $($a PPT adversary that violates the definition$).(10$ pts$)$

In practice, it is often the case that good block ciphers such as AES $($or some carefully designed hashes such as SHA$256)$ are assumed to be a PRF$.$ However, block cipher, by name, works on a fixed length of blocks, e$.$g$.,$ AES works on $128-$bit messages only. The followings are two possible ways to adjust the input$/$output length of a PRF$,$ prove that the constructions are still PRF according to the above definition.

Q$2$: Given a PRF E:K$\backslash$times $0,1$n$0,1$m$,$ we construct F:K$\backslash$times $0,1$n$-10,12$m as follows:

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

Is FK$,$ 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 $1$:$=($KeyGen$1,$ Tag$1,$ Verify$1)$ and $2$:$=($KeyGen$2,$ Tag$2,$ Verify$2)$ are two message authentication code schemes.

Q$6$: $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 $1$ and it runs Tag$2($k$2,$ m$1$m$2)$ and obtains $2,$ where the message m that Tag$3$ works on is a pair of messages m$1,$ m$2.$ The final tag is $31||2.$ The verification can be defined accordingly.

Is $3$ a secure MAC? Briefly explain why. $(10$ pts$)$

Q$7$: $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 $1$ and it runs Tag$2($k$,$ m$2)$ and obtains $2.$ The final tag is

$\backslash$sigma $12.$

Is $4$ a secure MAC? Briefly explain why. $(10$ pts$)$

Q$8$: Given two constructions of message authentication codes $1$:$=($KeyGen$1,$ Tag$1,$ Verify$1),2$:$=($KeyGen$2,$ Tag$2,$ Verify$2).$ Construct a secure MAC scheme $3$:$=($KeyGen$3,$ Tag$3,$ Dec$3)$ which will be secure $($unforgeable$)$ as long as one of $1,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 $.$ The final ciphertext will be $($c$,\backslash$sigma $).(15$ pts$)$