Consider the NMAC construction:

enter image description here

This is a proposed exercise in my notes:

Assume F is a PRP with $n = l(n)$. Is it secure to replace $k_0$ by $F_{0^n}(k_0)$ and $k_i$ by $F_{0^n}(k_i)$?

In principle, I think I should prove it is not secure. My second guess is that probably I should find some non-prefix free query. However, I didn't find a solution. Any hints?

Here is my definition of PRP:

enter image description here

  • $\begingroup$ Suppose $k_0$ is uniformly distributed. if $F$ is a PRP, what is the distribution on $F_{0^n}(k_0)$? $\endgroup$ Feb 18 '19 at 19:15
  • $\begingroup$ @SqueamishOssifrage it should be uniform but for a negligible probability. Does this means that the MAC is still secure? $\endgroup$
    – Rodrigo
    Feb 18 '19 at 21:46
  • $\begingroup$ What is that negligible probability? (Hint: It is a very simple constant. Is the pseudorandom property of the PRP even relevant?) $\endgroup$ Feb 18 '19 at 22:06
  • $\begingroup$ @SqueamishOssifrage The definition of PRP tells me, that any distinguisher should have negligible advantage in distinguishing it from a RPO. Of course, this pseudorandom property would be not relevant if i assume i have a strong PRP and in that case I could say $F_{0^n}(k_0)$ has a uniform distribution. If you can confirm me this is your line of thougth then I guess that with this we are proving that it is as secure as F-NMAC and thus is a secure MAC for $F$ a PRP. $\endgroup$
    – Rodrigo
    Feb 19 '19 at 13:36
  • $\begingroup$ @SqueamishOssifrage If the above is correct probably a PRP is required in this setting to avoid collision of $F_{0^n}(k_i)$ and $F_{0^n}(k_o)$ $\endgroup$
    – Rodrigo
    Feb 19 '19 at 13:38

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.