Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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



Mridul Nandi


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 Dates
August 16-20, 2009
Conference Location
Santa Barbara, CA
Conference Title


Domain Extension, PRF, PRP, CBC, OMAC


Nandi, M. (2009), Valid Affine Domain Extensions: Improving upon Security Bound of PRP-based PRFs, Crypto-2009, Santa Barbara, CA (Accessed May 30, 2023)
Created August 17, 2009, Updated February 19, 2017