NIST logo

Publication Citation: Valid Affine Domain Extensions: Improving upon Security Bound of PRP-based PRFs

NIST Authors in Bold

Author(s): Mridul Nandi;
Title: Valid Affine Domain Extensions: Improving upon Security Bound of PRP-based PRFs
Published: August 17, 2009
Abstract: This paper provides an improved security analysis of popular pseudorandom functions (PRF) based on an $n$-bit pseudorandom permutation (PRP). In CRYPTO-05, an improved security analysis of \tx{CBC} (with prefix-free message space) was shown. The similar improved security analysis was subsequently made for other variants (e.g., \tx{XCBC}, \tx{TMAC}, and \tx{PMAC}). Letting $\ell$ be the number of blocks of the longest query among all $q$ queries, all these shown improved bounds are roughly $\ell q^2/2^n$, improving their prior bounds of $\ell^2 q^2/2^n$. We provide a general framework of this direction of research. In this paper, all these aforementioned constructions and their different neighbors are unified (based on relationships between intermediate inputs and intermediate outputs) by defining a new class of domain extensions, called class of affine domain extensions (\tx{ADE}). We characterize all intuitive insecure domain extensions as: there are two messages $M$ and $M'$ and an integer $i$, so that $i\th$ intermediate output of $M'$ is same as the final output of $M$ with probability one. We prove that all other affine domain extensions, called {\em valid affine domain extensions} or \tx{VADE}, are PRF. More importantly, we present an improved PRF-security analysis of all \tx{VADE}. As an immediate application, we provide an improved security bound for \tx{OMAC} of the form $\ell q^2 / 2^n$ (or of the better form $\sigma q /2^n$ whenever $\ell < 2^{n/4}$, $\sigma$ is the total number of blocks present in all $q$ queries). Before this, no such improved bound for \tx{OMAC} is known. Our improved security analysis similarly works for \tx{CBC} (with prefix-free messages) and \tx{PMAC} to obtain improved bounds about $\sigma q /2^n$.
Conference: Crypto-2009
Location: Santa Barbara, CA
Dates: August 16-20, 2009
Keywords: Domain Extension; PRF; PRP; CBC; OMAC
Research Areas: Information Technology