Paper 2022/905

Tight Security Analysis of the Public Permutation-Based PMAC_Plus

Avijit Dutta, Institute for Advancing Intelligence, TCG-CREST
Mridul Nandi, Indian Statistical Institute
Suprita Talnikar, Indian Statistical Institute

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.

Available format(s)
Secret-key cryptography
Publication info
PMAC_Plus Public Permutation PRF from PRP Sum-Capture Lemma H-Coefficient Technique
Contact author(s)
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com
2022-07-12: last of 2 revisions
2022-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Avijit Dutta and Mridul Nandi and Suprita Talnikar},
      title = {Tight Security Analysis of the Public Permutation-Based PMAC_Plus},
      howpublished = {Cryptology ePrint Archive, Paper 2022/905},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.