[Resource Topic] 2022/689: Tight Multi-User Security Bound of $\textsf{DbHtS}$

Welcome to the resource topic for 2022/689

Tight Multi-User Security Bound of \textsf{DbHtS}

Authors: Nilanjan Datta, Avijit Dutta, Mridul Nandi, and Suprita Talnikar


In CRYPTO’21, Shen et al. have proved in the ideal cipher model that \textsf{Two-Keyed-DbHtS} construction is secure up to 2^{2n/3} queries in the multi-user setting independent of the number of users, where the underlying double-block hash function \textsf{H} of the \textsf{Two-Keyed-DbHtS} construction is realized as the concatenation of two independent n-bit keyed hash functions (\textsf{H}_{K_h,1}, \textsf{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 the key-reduced variants of \textsf{DbHtS} MACs, including \textsf{2K-SUM-ECBC}, \textsf{2K-PMAC_Plus} and \textsf{2K-LightMAC_Plus} without requiring domain separation technique and proved 2n/3-bit multi-user security of these constructions in the ideal cipher model. Recently, Guo and Wang have invalidated the security claim of Shen et al.'s result by exhibiting three constructions, which are the instantiations of the \textsf{Two-Keyed-DbHtS} framework, such that each of their n-bit keyed hash functions being O(2^{-n}) universal and regular, while the constructions themselves are secure only up to the birthday bound. In this work, we show a sufficient condition on the underlying Double-block Hash (\textsf{DbH}) function, under which we prove 3n/4-bit multi-user security of the \textsf{Two-Keyed-DbHtS} construction in the ideal-cipher model. As an instantiation, we show that two-keyed Polyhash-based \textsf{DbHtS} construction is multi-user secure up to 2^{3n/4} queries in the ideal-cipher model. Furthermore, due to the generic attack on \textsf{DbHtS} constructions by Ga"etan et al. in CRYPTO’18, our derived bound for the construction is tight.

ePrint: https://eprint.iacr.org/2022/689

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .