Paper 2022/689

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

Abstract

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.

Note: We have revised the paper after incorporating the review comments of ToSC 2023, Issue I