Paper 2022/905

Tight Security Analysis of the Public Permutation-Based PMAC_Plus

Abstract

Yasuda proposed a variable input-length PRF in CRYPTO 2011, called $\mathsf{\text{PMAC\_Plus}}$, based on an $n$-bit block cipher. $\mathsf{\text{PMAC\_Plus}}$ is a rate-$1$ construction and inherits the well-known $\mathsf{\text{PMAC}}$ parallel network with a low additional cost. However, unlike $\mathsf{\text{PMAC}}$, $\mathsf{\text{PMAC\_Plus}}$ is secure roughly up to $2^{2n/3}$ queries. Zhang et al. proposed \textsf{3kf9} in ASIACRYPT 2012, Naito proposed \textsf{LightMAC_Plus} in ASIACRYPT 2017, and Iwata et al. proposed \textsf{GCM-SIV2} in FSE 2017 -- all of them secure up to around $$ queries. Their structural designs and corresponding security proofs were unified by Datta et al. in their framework {\em Double-block Hash-then-Sum} (\textsf{DbHtS}). Leurent et al. in CRYPTO 2018 and then Lee et al. in EUROCRYPT 2020 established a tight security bound of $$ on \textsf{DbHtS}. That $$ provides security for roughly up to $$ queries is a consequence of this result. In this paper, we propose a public permutation-based variable input-length PRF called $$. We show that $$ is secure against all adversaries that make at most $$ queries. We also show that the bound is essentially tight. It is of note here that instantiation of each block cipher of $$ with the two-round iterated Even-Mansour cipher can yield a beyond the birthday bound secure PRF based on public permutations. Altogether, the solution incurs $$ permutation calls, whereas our proposal requires only $$ permutation calls, $$ being the maximum number of message blocks.