Cryptology ePrint Archive: Report 2021/097

A New and Improved Reduction Proof of Cascade PRF

Mridul Nandi

Abstract: The prefix-free security of a cascade function based on a $c$-bit compression function $f$ is reduced to the $q$-query PRF security of $f$ with a tightness gap $\ell q$ where $q$ represents the maximum number of queries to the cascade and $\ell$ represents the length of the longest query. A two-stage proof for this reduction was first given by Bellare et al. in FOCS-96 for an adaptive distinguisher, and later a similar two-stage reduction was proved in CRYPTO-14 by Gazi et al. for a non-adaptive distinguisher.

In this paper we prove a direct single-stage reduction with a tightness gap of $\sigma$ (the total length of all queries). This is an improvement over existing reductions whenever the lengths of queries vary widely. In the case of non-adaptive prefix-free security, we also show a reduction proof which reduces PRF advantage of the cascade to two terms -- (i) a $q$-query PRF security of $f$ with a tightness gap of $q$ (without a factor of $\ell$) and (ii) a single query PRF security of $f$ with a tightness gap of $\sigma$. We further extend to a more general finer reduction to multiple terms over different limits on the queries to $f$. All these reductions can be easily extended to a multiuser setup. In particular, we reduce multiuser prefix-free PRF security of the cascade to a single user $q_{\max}$-query PRF security of $f$ with a tightness gap $\overline{\sigma}$ (the total length of all queries to all users), where $q_{\max}$ is the maximum number of queries allowed to any user. We have shown similar improved bounds (with respect to query complexity) for non-adaptive multiuser PRF security. In addition to immediate applications to multiuser security of HMAC and NMAC, our improved analysis has the following useful applications:

1. We show that the multiuser non-adaptive PRF security of the cascade does not degrade even if $f$ assures a weaker non-adaptive PRF security advantage.

2. The PRF security of single-keyed NMAC and Envelope MAC can be reduced to the non-adaptive multiuser prefix-free PRF security of the cascade construction and hence all improved reductions are applicable to these constructions. As a result, the constants ipad and opad used in HMAC are redundant. Moreover, the existing PRB assumption on $f$ can be replaced by a simple regular property for the constant-free HMAC.

Category / Keywords: foundations / PRF, HMAC, NMAC, cascade, non-adaptive security

Date: received 26 Jan 2021, last revised 26 Jan 2021

Contact author: mridul nandi at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210127:133753 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]