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

Published

August 17, 2009

Author(s)

Mridul Nandi

Abstract

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

Crypto-2009

Pub Type

Conferences

Keywords

PRF, non-adaptive adversary, cascade, EMD.

Citation

Nandi, M. (2009), PRF-Security Revisited With New Efficient Single-Keyed Domain Extensions, Crypto-2009, Santa Barbara, CA (Accessed October 14, 2025)