Information Security and Cryptography Research Group

Single-key AIL-MACs from any FIL-MAC

Ueli Maurer and Johan Sjödin

Automata, Languages and Programming — ICALP 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3580, pp. 472–484, Jul 2005.

We investigate a general paradigm for constructing arbitrary-input-length (AIL) MACs from fixed-input-length (FIL) MACs, define the waste as the relevant efficiency parameter of such constructions, and give a simple and general security proof technique applicable to very general constructions. We propose concrete, essentially optimal constructions for practical use, Chain-Shift (CS) and Chain-Rotate (CR), and prove their security. They are superior to the best previously known construction, the NI-construction proposed by An and Bellare: Only one rather than two secret keys are required, the efficiency is improved, and the message space is truly AIL, i.e., there is no upper bound on the message length. The generality of our proof technique is also illustrated by giving a simple security proof of the NI-construction and several improvements thereof.

BibTeX Citation

@inproceedings{MauSjo05a,
    author       = {Ueli Maurer and Johan Sjödin},
    title        = {Single-key {AIL-MAC}s from any {FIL-MAC}},
    editor       = {L. Caires},
    booktitle    = {Automata, Languages and Programming --- ICALP 2005},
    pages        = {472--484},
    series       = {Lecture Notes in Computer Science},
    volume       = {3580},
    year         = {2005},
    month        = {7},
    publisher    = {Springer-Verlag},
}

Files and Links