Paper 2022/304

Multi-User BBB Security of Public Permutations Based MAC

Yu Long Chen, Avijit Dutta, and Mridul Nandi


At CRYPTO 2019, Chen et al. have shown a beyond the birthday bound secure $n$-bit to $n$-bit PRF based on public random permutations. Followed by the work, Dutta and Nandi have proposed a beyond the birthday bound secure nonce based MAC $\textsf{nEHtM}_p$ based on public random permutation. In particular, the authors have shown that $\textsf{nEHtM}_p$ achieves tight $2n/3$-bit security ({\em with respect to the state size of the permutation}) in the single-user setting, and their proven bound gracefully degrades with the repetition of the nonces. However, we have pointed out that their security proof is not complete (albeit it does not invalidate their security claim). In this paper, we propose a minor variant of $\textsf{nEHtM}_p$ construction, called $\textsf{nEHtM}^*_p$ and show that it achieves a tight $2n/3$ bit security in the multi-user setting. Moreover, the security bound of our construction also degrades gracefully with the repetition of nonces. Finally, we have instantiated our construction with the PolyHash function to realize a concrete beyond the birthday bound secure public permutation-based MAC, $\textsf{nEHtM}_p^+$ in the multi-user setting.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Cryptography and Communications
Faulty NonceMirror TheoryPublic PermutationExpectation Method
Contact author(s)
yulong chen @ kuleuven be
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
2022-03-07: received
Short URL
Creative Commons Attribution


      author = {Yu Long Chen and Avijit Dutta and Mridul Nandi},
      title = {Multi-User BBB Security of Public Permutations Based MAC},
      howpublished = {Cryptology ePrint Archive, Paper 2022/304},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.