On the Full MAC Security of a Double-Piped Mode of Operation


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.1   pp.84-91
Publication Date: 2011/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.84
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Identification
domain extension,  unpredictability,  unforgeability,  message authentication code,  MAC,  birthday bound,  

Full Text: PDF>>
Buy this Article

We revisit the double-pipe construction introduced by Lucks at Asiacrypt 2005. Lucks originally studied the construction for iterated hash functions and showed that the approach is effective in improving security against various types of collision and (second-)preimage attacks. Instead, in this paper we apply the construction to the secret-key setting, where the underlying FIL (fixed-input-length) compression function is equipped with a dedicated key input. We make some adjustments to Lucks' original design so that now the new mode works with a single key and operates as a domain extension of MACs (message authentication codes). Though more than twice as slow as the Merkle-Damgård construction, the double-piped mode enjoys security strengthened beyond the birthday bound. More specifically, when iterating an FIL-MAC whose output size is n-bit, the new double-piped mode yields an AIL-(arbitrary-input-length-)MAC with security up to O(2n) query complexity. This bound contrasts sharply with the birthday bound of O(2n/2), which was the best MAC security accomplished by earlier constructions.