Paper 2025/1351

On the Regularity of the Generalized Birthday Problem

Abstract

The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. While the $k$-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ (NDSS'16) utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. Our work reveals that the $k$-list $\textsf{GBP}$ implicitly exhibits a regularity property, a block-wise structure that has been thoroughly studied by Esser and Santini (Crypto'24) in the context of the Syndrome Decoding Problem. Such structured regularity can often be leveraged to design efficient protocols and enable new functionalities. In this work, we revisit these two long-conflated $\textsf{GBP}$s and initiate a systematic study of the regularity in the realm of $\textsf{GBP}$. $\textbf{Complexity.}$ In the worst-case setting, we develop a novel ISD-based framework for $\textsf{GBP}$. When $k/n > 0.188$ and $k/n > 0.11$ for the regular and non-regular cases, respectively, the proposed algorithms surpass the worst-case complexity of $2^{n/2}$. Through numerical optimization, we heuristically demonstrate that for any constant $k/n > 0$, the advanced ISD algorithms such as BJMM achieve an asymptotic complexity superior to the birthday bound when applied to density-one $\textsf{GBP}$ instances. Our results disprove the average-case-to-worst-case $k$-$\textsf{XOR}$ conjecture when $k$ is non-constant (e.g., linear in $n$). In the average-case regime, we fill in theoretical gaps in solving the single-list $\textsf{GBP}$ and show that the regular variant exhibits a $\sqrt{2}$-factor difference in the exponent, which extends naturally to the $k$-$\textsf{SUM}$ problem and offers new insights into its complexity. $\textbf{Implications for Cryptography.}$ We analyze the impact of regularity on incremental hash and propose a new collision attack against the ID-based incremental hash (Eurocrypt'97). Our attack achieves an asymptotic time complexity of $\mathcal{O}(\sqrt{n} \cdot 2^{\sqrt{2n}})$, significantly improving upon Wagner's previous bound of $\mathcal{O}(2^{\sqrt{4n}})$ (Crypto'02). Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from $2^{256}$ to $2^{189}$. In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. To address this, we propose $\textsf{Requihash}$, a PoW with enhanced ASIC-resistance and a smaller solution size, rigorously aligned with the regular $k$-list $\textsf{GBP}$.

Note: This is the full version of the paper appearing in the conference proceedings.