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 $\textsf{PMAC_Plus}$, based on an $n$-bit block cipher. $\textsf{PMAC_Plus}$ is a rate-$1$ construction and inherits the well-known $\textsf{PMAC}$ parallel network with a low additional cost. However, unlike $\textsf{PMAC}$, $\textsf{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 $2^{2n/3}$ 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 $2^{3n/4}$ on \textsf{DbHtS}. That $\textsf{PMAC_Plus}$ provides security for roughly up to $2^{3n/4}$ queries is a consequence of this result. In this paper, we propose a public permutation-based variable input-length PRF called ${\textsf{pPMAC_Plus}}$. We show that ${\textsf{pPMAC_Plus}}$ is secure against all adversaries that make at most $2^{2n/3}$ queries. We also show that the bound is essentially tight. It is of note here that instantiation of each block cipher of ${\textsf{pPMAC_Plus}}$ 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 $(2\ell + 4)$ permutation calls, whereas our proposal requires only $(\ell+2)$ permutation calls, $\ell$ being the maximum number of message blocks.