# A modification of the NMAC construction

Consider the NMAC construction:

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:

• Suppose $k_0$ is uniformly distributed. if $F$ is a PRP, what is the distribution on $F_{0^n}(k_0)$? Feb 18 '19 at 19:15
• @SqueamishOssifrage it should be uniform but for a negligible probability. Does this means that the MAC is still secure? Feb 18 '19 at 21:46
• What is that negligible probability? (Hint: It is a very simple constant. Is the pseudorandom property of the PRP even relevant?) Feb 18 '19 at 22:06
• @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. Feb 19 '19 at 13:36
• @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)$ Feb 19 '19 at 13:38