Revisiting Vector-Input MACs

At Eurocrypt 2006, Rogaway and Shrimpton (RS06) presented the idea of vector-input MAC that accepts a vector consisting of variable-length bit strings. A vector-input MAC could be built on a conventional (bit) string-input MAC, e.g., CMAC, with an injective encoding. RS06 pointed out an efficiency loss in this method and presented a general construction S2V that is more efficient than the encodingbased method. RS06 made significant scientific and practical impacts on the field of mode constructions, in particular for the invention of deterministic authenticated encryption. However, despite its potential, their work on vector-input MAC has been largely overlooked for more than 18 years. We revisit RS06’s treatment of vector-input MAC and show that the topic is more subtle than initially considered. We first formally define the problem of vector-input MAC and propose a natural efficiency goal for vector-input MACs as a counterpart of what has been considered for string-input MACs. Since S2V with any string-input MAC mode never achieves this efficiency goal, we propose a family of new MAC modes, VecMAC, that achieves this goal. VecMAC has a similarity to the popular PMAC, in particular its idea of tweak. However, the purpose of introducing tweak is different from PMAC and tweak is tailored to handle vectors without redundant block cipher calls. We also provide implementation results that show an advantage over the conventional method.