Paper 2020/509

BBB Secure Nonce Based MAC Using Public Permutations

Avijit Dutta and Mridul Nandi


In the recent trend of CAESAR competition and NIST light-weight competition, cryptographic community have witnessed the submissions of several cryptographic schemes that are build on public random permutations. Recently, in CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing beyond birthday bound PRFs from public random permutations and they proposed two instances of such PRFs. In this work, we extend this research direction by proposing a nonce-based MAC build from public random permutations. We show that our proposed MAC achieves $2n/3$ bit security (with respect to the state size of the permutation) and the bound is essentially tight. Moreover, the security of the MAC degrades gracefully with the repetition of the nonce.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. AFRICACRYPT 2020
Faulty NonceMirror TheoryPublic PermutationExpectation Method
Contact author(s)
avirocks dutta13 @ gmail com
2020-05-05: received
Short URL
Creative Commons Attribution


      author = {Avijit Dutta and Mridul Nandi},
      title = {BBB Secure Nonce Based MAC Using Public Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2020/509},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.