A Lightweight Alternative to PMAC

摘要

PMAC is a parallelizable message authentication code (MAC) based on a block cipher. PMAC has many desirable features, such as parallelizability and essential optimality in terms of the number of block cipher calls, and the provable security. However, PMAC needs a pre-processing of one block cipher call taking all-zero block to produce the input masks to all subsequent block cipher calls. This incurs an overhead for both time and memory, which is often non-negligible. In particular, this makes PMAC's state size 3n bits, 'lb address these issues, we propose a new parallelizable MAC as an alternative to PMAC, which we call LAPMAC. LAPMAC enables a high parallelizability, and unlike PMAC, it does not need a pre-processing to create an input mask. This leads to 2n-bit state memory compared to PMAC's 3n-bit state. Moreover, LAPMAC is highly optimized in terms of the number of block cipher calls, for example it requires exactly the same number of block cipher calls as PMAC when one pre-processing call is allowed, and achieves the same number of block cipher calls as the state-of-the-art serial MACs those do not need the pre-processing call. We prove that LAPMAC is secure up to around 2_(n/2) queried blocks, under the standard pseudorandomness assumption of the underlying block cipher.