Tight Multi-User Security Bound of sfDbHtS

. In CRYPTO’21, Shen et al. have proved that DbHtS is secure up to 2 2 n/ 3 queries in the multi-user setting independent of the number of users, where the double block hash function H consists of two independent n -bit keyed hash function ( H K h , 1 , H K h , 2 ) such that each of the n -bit keyed hash function is O (2 − n ) universal and regular. They have also demonstrated the applicability of their result to key-reduced variants of DbHtS MACs including 2K-SUM-ECBC , 2K-PMAC_Plus and 2K-LightMAC_Plus without requiring any additional domain separation. Recently, Guo and Wang have shown three instantiations of DbHtS framework where each of their n -bit keyed hash functions is O (2 − n ) universal and regular but the constructions are itself secure only up to the birthday bound. In this work, we show a suﬃcient condition on the underlying Double-block Hash ( DbH ) function under which we prove 3 n/ 4-bit multi-user security of DbHtS construction in the ideal-cipher model. As an instantiation, we show that Polyhash based DbHtS construction is multi-user secured up to 2 3 n/ 4 queries in the ideal-cipher model. Moreover, due to the result of the generic attack on DbHtS constructions by Gaëtan et al. in CRYPTO’18, our derived bound for the construction is tight.