Paper 2024/731
Tight Security of Double-Block Nonce-Based MACs
Abstract
In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool, namely extended Mirror theory based on two independent permutations to a wide range of $\xi_{\max}$ including inequalities. Furthermore, we give a generic semi-black-box reduction from single-user security bound in the standard model to multi-user security bound in the ideal cipher model, yielding significantly better bounds than the naive hybrid argument. This reduction is applicable to all MAC construction we considered in this paper and even can be more generalized. We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- message authentication codebeyond birthday bound securityMirror theory
- Contact author(s)
-
wonseok @ purdue edu
hicalf @ kaist ac kr
yeongmin lee @ desilo ai - History
- 2024-05-16: approved
- 2024-05-13: received
- See all versions
- Short URL
- https://ia.cr/2024/731
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/731, author = {Wonseok Choi and Jooyoung Lee and Yeongmin Lee}, title = {Tight Security of Double-Block Nonce-Based {MACs}}, howpublished = {Cryptology ePrint Archive, Paper 2024/731}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/731}}, url = {https://eprint.iacr.org/2024/731} }