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

Published

August 17, 2009

Author(s)

Mridul Nandi

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 Dates

August 16-20, 2009

Conference Location

Santa Barbara, CA

Conference Title

Crypto-2009

Pub Type

Conferences

Keywords

Domain Extension, PRF, PRP, CBC, OMAC

Citation

Nandi, M. (2009), Valid Affine Domain Extensions: Improving upon Security Bound of PRP-based PRFs, Crypto-2009, Santa Barbara, CA (Accessed April 18, 2024)