Paper 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.