Let $ G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a length doubling PRG, and let $ \Pi=(Gen,Mac,Vrfy)$ be the following MAC scheme:

$ Gen $ on input $ 1^n$ uniformly samples and outputs $ k\leftarrow \{0,1\}^n $.

$ Mac $ on input $k\in\{0,1\}^n$ and message $m\in \{0,1\}^n$ outputs $ t=G(k||m) $.

$ Vrfy $ on input $k\in\{0,1\}^n$, message $m\in \{0,1\}^n$ and a tag $ t\in \{0,1\} ^{4n}$outputs 1 if $ t=G(k||m) $ and outputs 0 otherwirse.

Is $ \Pi $ necessarily a secure MAC scheme?

  • $\begingroup$ what kind of secure? $\endgroup$ – dandavis Apr 9 '17 at 4:11
  • $\begingroup$ ...and what security definition for PRG are you using? $\endgroup$ – Elias Apr 9 '17 at 19:34
  • $\begingroup$ Adding to @Elias' point, what jumps out to me is that PRG definitions generally stipulate that the output to is secure if the input is sampled uniformly at random from the whole domain. $\endgroup$ – Luis Casillas May 2 '17 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.