Paper 2017/852
Blockcipher-based MACs: Beyond the Birthday Bound without Message Length
Yusuke Naito
Abstract
We present blockcipher-based MACs (Message Authentication Codes) that have beyond the birthday bound security without message length in the sense of PRF (Pseudo-Random Function) security. Achieving such security is important in constructing MACs using blockciphers with short block sizes (e.g., 64 bit). Luykx et al. (FSE2016) proposed LightMAC, the first blockcipher-based MAC with such security and a variant of PMAC, where for each $n$-bit blockcipher call, an $m$-bit counter and an $(n-m)$-bit message block are input. By the presence of counters, LightMAC becomes a secure PRF up to $O(2^{n/2})$ tagging queries. Iwata and Minematsu (TOSC2016, Issue1) proposed F_t, a keyed hash function-based MAC, where a message is input to $t$ keyed hash functions (the hash function is performed $t$ times) and the $t$ outputs are input to the xor of $t$ keyed blockciphers. Using the LightMAC's hash function, F_t becomes a secure PRF up to $O(2^{t n/(t+1)})$ tagging queries. However, for each message block of $(n-m)$ bits, it requires $t$ blockcipher calls. In this paper, we improve F_t so that a blockcipher is performed only once for each message block of $(n-m)$ bits. We prove that our MACs with $t \leq 7$ are secure PRFs up to $O(2^{t n/(t+1)})$ tagging queries. Hence, our MACs with $t \leq 7$ are more efficient than F_t while keeping the same level of PRF-security.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in ASIACRYPT 2017
- Keywords
- MACblockcipherPRFPRPbeyond the birthday boundmessage lengthcounter
- Contact author(s)
- Naito Yusuke @ ce mitsubishielectric co jp
- History
- 2017-09-09: received
- Short URL
- https://ia.cr/2017/852
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/852, author = {Yusuke Naito}, title = {Blockcipher-based {MACs}: Beyond the Birthday Bound without Message Length}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/852}, year = {2017}, url = {https://eprint.iacr.org/2017/852} }