Paper 2022/689

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

Nilanjan Datta, Institute for Advancing Intelligence, TCG-CREST
Avijit Dutta, Institute for Advancing Intelligence, TCG-CREST
Mridul Nandi, Indian Statistical Institute
Suprita Talnikar, Indian Statistical Institute

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 2022, Issue 3

Available format(s)
Secret-key cryptography
Publication info
DbHtS PRF Polyhash H-Coefficient Technique Mirror Theory.
Contact author(s)
nilanjan_isi_jrf @ yahoo com
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com
2022-07-12: last of 2 revisions
2022-05-31: received
See all versions
Short URL
No rights reserved


      author = {Nilanjan Datta and Avijit Dutta and Mridul Nandi and Suprita Talnikar},
      title = {Tight Multi-User Security Bound of $\textsf{DbHtS}$},
      howpublished = {Cryptology ePrint Archive, Paper 2022/689},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.