TL;DR: We study structural regularity in the Generalized Birthday Problem and its impact on practical schemes including incremental hashing and Equihash. The main contribution of this work is the complexity analysis of regular and non-regular GBP, with important implications for the $k$-$\textsf{XOR}$ and $k$-$\textsf{SUM}$ problems.

TL;DR: We propose a new list-item-reduction framework that reduces the memory complexity of Wagner’s algorithm from $2nN$ to $nN$ bits, thereby weakening the ASIC resistance of Equihash. This optimization has important implications for the efficient implementation of Wagner-style algorithms.

TL;DR: We extend post-retrieval to Wagner’s $k$-tree algorithm, reducing peak memory from exponential in $k$ to $O(k^2\ell N)$ with only linear time overhead. Applied to preimage attacks on incremental hashes, this trade-off can substantially reduce their memory–time cost.