Security of message authentication codes in the presence of key-dependent messages

In recent years, the security of encryption and signature schemes in the presence of key-dependent plaintexts received attention, and progress in understanding such scenarios has been made. In this article we motivate and discuss a setting where an adversary can access tags of a message authentication code (MAC) on key-dependent message inputs, and we propose a way to formalize the security of MACs in the presence of key-dependent messages (KD?EUF). Like signature schemes, MACs have a verification algorithm, and hence the tagging algorithm must be stateful. We present a scheme MAC-ver which offers KD?EUF security and also yields a forward-secure scheme.