International Association
for Cryptologic Research

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. Wagner's \(k\)-list algorithm (Crypto'02) for $\textsf{GBP}$ has advanced the optimization of solving the syndrome decoding problem and established new cryptanalytic benchmarks for incremental cryptography and blind signatures. $\textsf{Equihash}$ (NDSS'16) underscores the critical advantages of $\textsf{GBP}$ in proof-of-work design, particularly its ASIC-resistance in blockchain. While the k-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. In this work, we revisit these two long-conflated problems and fill in theoretical gaps in solving the single-list $\textsf{GBP}$.

In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. Our trade-off optimization to Wagner's algorithmic framework further diminishes this resistance by reducing peak memory by at least 50% across most $\textsf{Equihash}$ parameters. To address this, we propose $\textsf{Sequihash}$, a PoW with enhanced ASIC-resistance, rigorously aligned with the $k$-list $\textsf{GBP}$. Furthermore, we explore the implications of $\textsf{GBP}$ in the field of incremental hash and propose a new collision attack on 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 the previous Wagner's bound of $\mathcal{O}(2^{\sqrt{4n}})$. Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from \( 2^{256} \) to \( 2^{189} \).