$(8$ points$)$ Recall the standard security game for MACs. In this problem, we introduce

a new game called $$MAC security with random queries$.$ The security game proceeds

much like the standard security game except that each time the attacker requests a

forgery, the challenger picks a random message M and signs it$.$ Then the attacker

gets the chosen message and the signature. $($The oracle can be queried a polynomial

in n number of times.$)$ To win, the attacker must forge on a message M $$ that was

not signed on in the query phase. $($The attacker picks M $$ itself.$)$

Assume there exists a secure MAC scheme with algorithms $($Setup$,$ Sign, Verify$),$ where

the message space is $\{0,1\}$n for security parameter n$.$ Describe a new scheme with

algorithms $($Setup$,$ Sign$,$ Verify$)$ that is secure in the $$MAC security with random

queries$$ game, but not the standard security game. Your new algorithms may call

the existing algorithms.