One of the practice problems I was given for an exam that I'm preparing for is as follows:
Let $\Pi$ be a secure, deterministic MAC that uses canonical verification. Show how to construct a MAC $\Pi'$ that is secure and deterministic but is not strongly secure.
In my book, it says that if a MAC uses canonical verification, then it is a strong MAC. This seems to suggest that $\Pi'$ should not use canonical verification.
By the definition of a strongly secure MAC, for our construction, an adversary should be able to generate a new valid tag on an existing message-tag-pair that it has seen before. However, if the MAC is deterministic, doesn't that mean that each unique message only has one valid tag?
How do I approach such a construction? If all deterministic secure MACs can use canonical verification, and all secure MACs that use canonical verification are strongly secure, then doesn't that mean that all deterministic MACs are strongly secure?