Multi-user BBB security of public permutations based MAC

• Published in: Cryptography and communications 2022-09, Vol.14 (5), p.1145-1177
• Main Authors: Chen, Yu Long, Dutta, Avijit, Nandi, Mridul
• Format: Article
• Language: English
• Subjects: Birthdays; Circuits; Coding and Information Theory; Communications Engineering; Computer Science; Data Structures and Information Theory; Information and Communication; Mathematics of Computing; Networks; Permutations; Repetition; Security
• ISSN: 1936-2447; 1936-2455
• DOI: 10.1007/s12095-022-00571-w

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 nEHtM p based on public random permutation. In particular, the authors have shown that nEHtM p achieves tight 2 n /3-bit security ( 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 nEHtM p construction, called nEHtM p ∗ and show that it achieves a tight 2 n /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, nEHtM p + in the multi-user setting.