Paper 2010/014

A Unified Method for Improving PRF Bounds for a Class of Blockcipher based MACs

Mridul Nandi

Abstract

This paper provides a unified framework for {\em improving} \PRF(pseudorandom function) advantages of several popular MACs (message authentication codes) based on a blockcipher modeled as \tx{RP} (random permutation). In many known MACs, the inputs of the underlying blockcipher are defined to be some deterministic affine functions of previously computed outputs of the blockcipher. Keeping the similarity in mind, we introduce a class of \tx{ADE}s (affine domain extensions) and a wide subclass of \tx{SADE}s (secure \tx{ADE}) containing $\mathcal{C} = \{ \tx{CBC-MAC},\ \tx{GCBC}^*,\ \tx{OMAC},\ \tx{PMAC} \}$. We define a parameter $N(t,q)$ for each domain extension and show that all \tx{SADE}s have \PRF advantages $O(tq/2^n + N(t,q)/2^n)$ where $t$ is the total number of blockcipher computations needed for all $q$ queries. We prove that \PRF advantage of any \tx{SADE} is $O(t^2/2^n)$ by showing that $N(t,q)$ is always at most ${t \choose 2}$. We provide a better estimate $O(tq)$ of $N(t,q)$ for all members of $\mathcal{C}$ and hence these MACs have {\em improved advantages $O(tq / 2^n)$}. Our proposed bounds for \tx{CBC-MAC} and $\tx{GCBC}^*$ are better than previous best known bounds.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
affine domain extensionPRFrandom permutationCBC-MAC.
Contact author(s)
mridul nandi @ gmail com
History
2010-01-12: received
Short URL
https://ia.cr/2010/014
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/014,
      author = {Mridul Nandi},
      title = {A Unified Method for Improving PRF Bounds for a Class of Blockcipher based MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2010/014},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/014}},
      url = {https://eprint.iacr.org/2010/014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.