Skip to main content
9 of 14
Straighten it; hopefully!
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

My reading is that one can't exhibit the counter example asked.

Applying a secure PRF $F_{k_2}$ with random secret constant $k_2$ to the output of a public collision-resistant function $H$ yields a secure MAC (only at worst slightly less secure than the weakest of $F$ and $H$).

And that holds a fortiori if $H$ is $H_{k_1}$ with $k_1$ random and secret, given that, per comment, $H_{k_1}$ is collision-resistant for fixed (random public) $k_1$.

The proposition in the butlast paragraph holds because distinguishing $F_{k_2}(H(m_i))$ from random, for random secret $k_2$ and chosen distinct messages $m_i$, requires breaking the indistinguishability of $F_{k_2}$ or the collision-resistance of the public function $H$. Proof sketch of that: for hypothetical distinct messages $m_i$ allowing to distinguish $F_{k_2}(H(m_i))$ from random, if there is a collision among the $h_i=H(m_i)$, and since $H$ is public, that exhibits a pair of $h_i$ breaking the collision-resistance of $H$; otherwise, we can distinguish the $F(h_i)$ from random for chosen distinct $h_i$, thus breaking the indistinguishability of $F$.

fgrieu
  • 145.5k
  • 12
  • 319
  • 611