Problem $4-$ Basic Concept of PRF and MAC

In our lecture, we showed how to use pseudorandom function $($PRF$)$ to con$-$

struct message authentication code. The construction is simple, Tag $(sk,m)$ just

outputs sk$,m.$ The security intuitively follows from PRF$,$ as an adversary

cannot figure out $F(sk,m^{**})$ for any $m^{**}$ not queried by him. Note: here "can$-$

not figure out" implicitly requires some condition. You will notice that in the

following tasks.

Below there are two task:

We want to answer a high$-$level question: is this $($MAC$)$ construction

secure as long as $F$ is any secure PRF$?$ If yes, give a proof. If No$,$ give a

counter$-$example.

Let $F(*,*)$:$\{0,1{\}}^{128}\{0,1{\}}^{128}\{0,1{\}}^{128}$ be a secure PRF given to you.

Then construct another secure $PRF{F}^{\text{'}}(*,*)$:$\{0,1{\}}^{128}\{0,1{\}}^{128}\{0,1\}.$

At a high level, we want you to construct a PRF that outputs only one

bit, from a given PRF that outputs $128$ bits.