In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are equivalent(within some factor in the advantage).

However, I am a bit confused by this no-verify version of the game. I have already had some explanation on this but I am still lost... Informally it seems to me that since the verification algorithm doesn't appear anywhere in the game, nothing prevents me from defining a MAC that does some kind of verification (i.e conditions to accept or reject) but also behaves insecurely. For instance, the verification algorithm also broadcasts the MAC key.

My first (failed) attempt was, starting with a secure MAC $M$, create a new one $M'$ such that one of the tag values ($\tau$) will never be used. And modify the new verification algorithm to reject any $(m,\tau)$ and output the key on such input. However, this construction doesn't meet the correctness requirement, i.e the output is not a bit. Therefore this counter-example would not be valid

So my questions are as follows:

  1. Is it really OK, that the game doesn't use all of the algorithms and will remain secure as long as it is correct?

  2. What is wrong with my failed counter-example? Namely, is it or not possible to find a correct counter-example such that the verification algorithm behaves insecurely?


1 Answer 1

  1. Yes, it's really ok. I would recommend trying to read through section 6.2 and understand it better (and ask more questions if needed). They prove that for any adversary $\mathcal{A}$ who expects to be able to make $q$ verification queries, one can make an adversary $\mathcal{A}'$ who makes 0 queries, but still has "fairly high" advantage in a formal way.

  2. You are missing that the verification algorithm is a predicate --- it must return "true" on valid tags, and "false" on invalid tags. One cannot make it "broadcast the key" as this would make it return something other than true/false. So essentially the algorithm you suggest is not a verification algorithm, because it returns the incorrect type to be a verification algorithm.

  • $\begingroup$ Thanks for your answer! Regarding 1) My comment is not about the correctness of the proof. I agree with it. ;) My issue is with the "interpretation" of this result and the explicit guarantees of such a security definition in a higher level protocol such has a using such a MAC to construct an "authenticated channel" from an insecure one. Therefore 2) I was trying here to adapt the CPA counter example to this MAC scheme. I was also wondering couldn't we extend the notion of predicate to two discrete sets $R$, $A$ so that it is understood that $e\in R$ "means" true, and $e \in A$ is "false"? $\endgroup$ Apr 21, 2020 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.