In the Mac-forge experiment, the adversary is given access to a tag-generation oracle, which generates a tag for each message given by the adversary. The adversary's task is to generate a valid tag on a message that hasn't been queried to the tag-generation oracle before, in polynomial time. If the adversary can do so with a non-negligible probability, then the MAC scheme is insecure or broken.

My question is whether giving the adversary access to a verification oracle, i.e. an oracle the adversary queries with message-tag pairs and finds out whether it's a valid tag for the corresponding message, reduces the security of the MAC scheme or not. Clearly, if the tag generation algorithm is deterministic, then the verification oracle gives nothing new, but if the tag-generation is randomized, is it still the same?

  • 2
    $\begingroup$ cstheory.stackexchange.com/q/20939/6973 ​ ​ $\endgroup$ – user991 Feb 17 '16 at 4:29
  • $\begingroup$ Also, if [there is a MAC scheme that's secure against adversaries that don't have a verification oracle] then there is a MAC scheme with deterministic tagging algorithm such that [a verification oracle lets an adversary very easily break the scheme] and [the scheme is otherwise secure]. ​ ​ $\endgroup$ – user991 Feb 17 '16 at 4:32

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.