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
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in TOSC 2023
- Keywords
- DbHtSPRFPolyhashH-Coefficient TechniqueMirror Theory.
- Contact author(s)
-
nilanjan_isi_jrf @ yahoo com
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
suprita45 @ gmail com - History
- 2023-02-07: last of 3 revisions
- 2022-05-31: received
- See all versions
- Short URL
- https://ia.cr/2022/689
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/689,
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{https://eprint.iacr.org/2022/689}},
url = {https://eprint.iacr.org/2022/689}
}
