Definition. Regular Generalized Birthday Problem. $\textsf{RGBP}(n, K)$: Given $K$ lists $L_1, \ldots, L_K$ containing random $n$-bit values, the strict generalized birthday problem involves finding $x_1 \in L_1, \ldots, x_K \in L_K$ such that

$$ x_1 \oplus x_2 \oplus \cdots \oplus x_K = 0. $$

Definition. Loose Generalized Birthday Problem. $\textsf{LGBP}(n, K)$: Given a list $L$ containing random $n$-bit values, the loose generalized birthday problem involves finding $x_1, \ldots, x_K \in L$ such that

$$ x_1 \oplus x_2 \oplus \cdots \oplus x_K = 0. $$

The repository contains the codes that accompany the paper "Revisiting the Generalized Birthday Problem and Equihash: Single or K Lists?". The eprint version of the paper is available at eprint/2025/1351. In this work, we revisit the following two long-conflated problems and fill in theoretical gaps in solving the single-list variant of $\textsf{GBP}$.

• The estimating codes for our main analyzing results including time/memory complexity of Wagner's algorithmic framework, $\textsf{iSHAKE}$ and our new Proposal $\textsf{Requihash}$.
• The proof of concept codes for estimating the complexity of ISD for worst-case $\textsf{GBP}$ .
• The proof of concept Lee-Brickell ISD solver for solving concrete $\textsf{GBP}$/$k\textsf{-XOR}$ instances at density near 1.
• The proof of concept python codes implementing the optimized single-list algorithm, k-list algorithm.
• The linearization attacks for both $\textsf{LGBP}$ and $\textsf{RGBP}$ over $\mathbb{F}_2$.

Pre-requisites

Testing Env: Sagemath 10.6 with Python 3.11.9.

Additional Requisites :

pip install cryptographic_estimators rich tqdm prettytable
# or 
pip install -r requirements.txt

Estimating Codes

Codes for our analyzing results in sub-directory /esitmator:

• single-list-optimal-k.ipynb：the expected number of solutions for single-list algorithm. Support Lemma 2, 4 and Theorem 5.
• all-in-one-estimator.ipynb：our analysis codes for $\textsf{iSHAKE}$ and the summary of average-case and worst-case $\textsf{GBP}$ (Support Theorem 1, 2, 4, Figure 1, Table 1)
• regular-Equihash.ipynb： estimator for Proof-of-Works: $\textsf{Equihash}, \textsf{Requihash}$. (Support Table 3)

GBP Solvers

Proof-of-concept implementations in sub-directory /GBP-solver:

• k_list_algorithm.py : the implementation of optimized Wagner's k-list algorithm for $\textsf{RGBP}$, using index trimming.
• single_list_algorithm.py: the implementation of optimized single-list algorithm for $\textsf{LGBP}$, using index pointers and duplicate check.
• secondary_solutions.py: the codes to analyze the number of secondary solutions generated by the optimized single-list algorithm when $k \approx \sqrt{\frac{n}{2} + 1}$.
• isd_solver.py: Information Set Decoding for $\textsf{LGBP}$ (Support Proposition 1, 2, Theorem 1, 2).
• Others: some results of our scripts for verifying the correctness of our implementations.

It is important to note that our Python implementation serves merely as a proof of concept and does not represent the most memory-efficient implementations.

ISD Solver Output Examples:

====================Estimating Near Worst Case GBP====================
Lower bound N_L(n, k) = 119
Instance LGBP(96, 32) with input list size 126, Density: 1.03528577145457
Fastest ISD algorithm for GBP(96, 32) at N = 126 is 'Both-May estimator in depth 2 for syndrome decoding problem with (n,k,w) = (126,30,32) over Finite Field of size 2'
Estimated time complexity: 19.592363985369104
Estimated memory complexity: 14.010702925037368
====================Solving (Near) Worst Case GBP((96, 32))====================
Instance LGBP(96, 32) with input list size 126, Density: 1.03528577145457 with 10.4645187453190 solutions in expectation
G.dimensions() = (30, 126)
Linear code info:  [126, 30] linear code over GF(2)
Information-set decoder (Lee-Brickell) for [126, 30] linear code over GF(2) decoding exactly 32 errors 
Runtime Estimate:  0.16717814824776894
Note that the solution may not exist with constant probability and it will stuck in the loop.
Rerun this script if consuming time is much greater than 0.16717814824776894 seconds.
Decoding time: 0.05081677436828613 seconds
e.hamming_weight() = 32
Check H * e == y: True
====================Solving (Near) Worst Case GBP((96, 26))====================
Instance LGBP(96, 26) with input list size 150, Density: 1.00257895657683 with 1.18721385310247 solutions in expectation
G.dimensions() = (54, 150)
Linear code info:  [150, 54] linear code over GF(2)
Information-set decoder (Lee-Brickell) for [150, 54] linear code over GF(2) decoding exactly 26 errors 
Runtime Estimate:  3.7779569311774566
Note that the solution may not exist with constant probability and it will stuck in the loop.
Rerun this script if consuming time is much greater than 3.7779569311774566 seconds.
Decoding time: 0.8272128105163574 seconds
e.hamming_weight() = 26
Check H * e == y: True

Linearization Attacks

Support Theorem 3. Linearization Attacks for $\textsf{LGBP}$ and $\textsf{SGBP}$ in sub-directory /linearization-attacks:

• lgbp-linearization-attack.ipynb: the linearization attacks on $\textsf{LGBP}(n,k)$ with $k \ge \frac{n}{2}$.
• sgbp-linearization-attack-XHASH.ipynb: the linearization attacks on $\textsf{SGBP}(n,k)$ with $k \ge {n}$. We take XHASH as a concrete example to show this attack.