Recall the EUF$-$CMA game we used in the definition of security for MACs.

EUF$-$CMA$()$ :

Challenger generates key klarrKeyGen$(1^{}).$

For iin$[l]$ :

Adversary sends message $m_i,$

Challenger responds with $t_i$larrMAC$(1^{},k,m_i).$

Adversary outputs $(m,t).$

Adversary wins if Verify $(1^{},j,m,t)$ accepts and for all iin$[l]$:$(m,t)(m_i,t_i).$

The MAC scheme $($KeyGen$,$ MAC, Verify$)$ is secure if every PPT has only negligible advantage in

winning the above game. We say a MAC scheme is weakly secure if the same holds with the following

modified definition of the winning condition:

Adversary wins if Verify$(1^{},j,m,t)$ accepts and for all iin$[l]$:$m{m}_i.$

Consider the following MAC scheme constructed using a PRF $($Gen$,$ Eval$).$ For security parameter $,$

the keys of this PRF are $-$bit strings, and the output space of its functions is $\{0,1{\}}^{}.$ It is very similar

to the construction we saw in class, but has a few additions.

KeyGen $(1^{})$ :

Output key klarrGen$(1^{}).$

MAC$(1^{},k,m)$:${?}_{?}$

Output $($Eval $\{$:$(1^{},k,m),0).$

Verify $(1^{},k,m,(t,j))$ :

Accept iff:

$t=$Eval$(1^{},k,m),$ and,

$j=0$ or and the $j^{th}$ bit of $k$ is $0$