I am having trouble understanding where the count of "passes" come in. What constitutes a pass in the context of message authentication codes? How are single-pass MACs achieved?
I suspect the questioner is asking not about MAC's per say, but rather Authenticated Encryption (AE, and if there is additional data, AEAD). I've been wondering this myself, so I asked Phillip Rogaway of UC Davis, who is one of the creators of EAX - a "two pass" "online" operation mode for block ciphers that - since it provides AE (confidentiality and integrity in the same process) does not need a MAC.
His response is really quite helpful - so (with his permission) I'm quoting it here:
There's no standard and rigorous definition of "one pass" vs. "two pass" for AE / AEAD schemes. Focusing only on encryption and the processing of plaintext, people mean either of two things by the terms “one pass” and “two pass”:
“One pass” (or “online”) could mean that the algorithm is constructed so that you can process an arbitrary length plaintext, left-to-right, spitting out the corresponding bits of ciphertext, again left to right, as you go, while you use only constant memory. In this sense, EAX is one-pass. This notion is easy to make rigorous. “Two pass” would then be interpreted to mean that you can make due with two constant-memory left-to-right passes through the plaintext, but not one. And so on.
Alternatively, “two pass” might mean that, when a human being looks at the description of the mode, there is one logical part of the design, this comprising a significant portion of the computational cost, that is clearly designed for privacy; and there is another logical part of the design, again a significant portion of the computational cost, intended for authenticity. One pass would mean that you can’t partition things up like this: that the privacy and authenticity are more tightly interwoven (often with an “authentication tag” being computed cheaply as a byproduct of whatever else is going on for privacy). I don’t know any way to make this concept rigorous, but I think it’s the more traditional use. Under this (informal) notion, EAX is two-pass, despite it being online. To help separate these uses, and stop calling something “two pass” when it could easily be implemented so as to be online, my paper with Krovetz on OCB3 introduced, for sense (2), “integrated” and “composed” instead of “one pass” and “two pass”. I don’t think these terms caught on ;-)
And for the curious, the papers he refers to is (I think) The Software Performance of Authenticated-Encryption Modes
I found (after getting his answer) his FAQ quite helpful - especially this answer.