A function family (where is the key length, taken to be the security parameter) is a secure MAC family if any adversary (whose resources are bounded by a polynomial in ) succeeds in the following game only with negligible probability. A random -bit key is chosen; next can adaptively choose messages and receive the corresponding MAC values . succeeds if it manages to forge the MAC, i.e., if it outputs a pair where and . See [2] for more details.