Paper 2022/304

Multi-User BBB Security of Public Permutations Based MAC

Yu Long Chen, Avijit Dutta, and Mridul Nandi

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Cryptography and Communications
Keywords
Faulty NonceMirror TheoryPublic PermutationExpectation Method
Contact author(s)
yulong chen @ kuleuven be
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
History
2022-03-07: received
Short URL
https://ia.cr/2022/304
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/304,
      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{https://eprint.iacr.org/2022/304}},
      url = {https://eprint.iacr.org/2022/304}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.