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.

PRF-Security Revisited With New Efficient Single-Keyed Domain Extensions



Mridul Nandi


In this paper, we study a wide class of single-keyed domain extension algorithms, called generalized domain extension (\tx{GDE}), extending a keyed function $F_K : {0,1}^b \to {0,1}^n$ to a keyed function $\overline{F}_K : {0,1}^* \to {0,1}^n$, $K \in {0,1}^k$. We show that the PRF-advantage (for an adaptive adversary) of a \tx{GDE} is upper bounded by a probability of some bad event for a non-adaptive adversary. Unlike an adaptive adversarial model, a non-adaptive adversarial model is much easier to analyze due to lack of complicated dependency between queries and responses. We also propose two efficient modes for pseudorandom function (or PRF) having several interesting features. (1) $\tx{PWP}$ (parallelizable wide-pipe): For an $\ell$-block message, it needs two off-line invocations and $\ell+1$ online invocations of $F_K$ (of which $\ell$ invocations are completely parallel). More interestingly, it is PRF-secure up to $\min\{Q,2^n\}$ queries, where $F_K$ is PRF-secure up to $Q$ queries. (2) \tx{OMD} (One-key enveloped \MD): Similar to \tx{EMD}, it is a multi-property-preserving construction (preserving PRF, pseudorandom oracle (PRO), and collision-resistant). It is a single-keyed construction (unlike \tx{EMD} and \tx{NMAC}) having several security and performance advantages over different cascade constructions.
Conference Dates
August 16-20, 2009
Conference Location
Santa Barbara, CA
Conference Title


PRF, non-adaptive adversary, cascade, EMD.


Nandi, M. (2009), PRF-Security Revisited With New Efficient Single-Keyed Domain Extensions, Crypto-2009, Santa Barbara, CA (Accessed May 25, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 17, 2009, Updated February 19, 2017