Subexponential algorithms speed up dense pigeonhole problems
Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime
Data Structures and AlgorithmsComputational Complexity
Summary
Some computer problems always have a guaranteed answer because of basic counting rules, but finding that answer can take a long time. This paper looks at a family of such problems where you want to find collisions—two different inputs that produce the same output—and shows that when the input is very dense, there are new faster algorithms that find these collisions more quickly than before. The authors build on earlier work and adapt advanced mathematical techniques to make this possible. They also show that their new algorithms are close to the best possible in terms of speed.
What this means in practice
- •For cryptography engineers: Find collisions in lattice-based problems faster, improving cryptanalysis techniques for dense parameter settings.
- •For optimization software developers: Use new faster algorithms for dense lattice problems to accelerate solving related constrained optimization tasks.
A theory result. No direct application yet.
Authors
Jadwiga Czyżewska, Karolina Drabik, Marek Sokołowski, Karol Węgrzycki
Abstract
The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it. We ask whether problems in this class admit significantly faster algorithms in the \emph{dense regime}. More concretly, we study \emph{binary collision Short Integer Solution} (SIS): given a matrix $A\in\mathbb{Z}_q^{n\times m}$ with $m>n\log q$, the goal is to find distinct $\underline{\mathbf{x}},\underline{\mathbf{y}}\in\{0,1\}^m$ with $A\underline{\mathbf{x}}=A\underline{\mathbf{y}}\pmod q$. Brute-force enumeration can be used to find a collision in $q^{\mathcal{O}(n)} \operatorname{poly}(|I|)$ time, and no significantly faster algorithm for that problem is known. We present an algorithm running in time $q^{o(n)}\cdot\operatorname{poly}(|I|)$ whenever the density parameter $δ:= m/(n\log q)$ is $ω(1)$.\footnote{All logarithms are in base $2$, and $|I|$ is the binary input length.} Building on reductions of Sotiraki et al.~(FOCS~2018), we obtain corresponding algorithms for dense variants of weak constrained SIS, Equal Vector Sums, Minkowski, and Blichfeldt. Our algorithm adapts techniques of Bhati et al.~(FOCS~2026), who gave a subexponential algorithm for Equal Sums in the dense regime and proved a tight conditional lower bound. Their conditional lower bound easily transfers to SIS and shows that the running time of our algorithms is essentially optimal.