Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime

Introduction

The class PPP, introduced by Papadimitriou [14], formalizes search problems based on the pigeonhole principle. Its defining problem asks for either a collision (i.e., two distinct inputs with the same output) or an input that maps to zero, in a function whose input and output spaces have the same size. The pigeonhole principle guarantees that one of these outcomes exists, but finding it can still be hard.

The class PPP contains many natural problems, including Equal Sums, variants of Short Integer Solution (SIS), Minkowski, and Blichfeldt [14, 16].¹ It has a natural connection to cryptography: for example, collision-resistant hash functions fit naturally into this class [16]. We define the full versions of these problems in § 1.1 and the formal class definitions and lattice background are in § 2.

Each of these problems has variants in the subclass PWPP, including the versions studied below. This class uses the weak pigeonhole principle: the input circuit has fewer output bits than input bits, which guarantees a collision. This class has a PWPP-complete problem: Sotiraki, Zampetakis, and Zirdelis [16] introduced weak constrained SIS and proved that every problem in PWPP reduces to it in polynomial time.

Generic algorithms for these classes enumerate or randomly sample inputs, with exponential worst-case running time in the number of output bits. We therefore ask if we can have better algorithms when the number of input bits is much larger than the number of output bits. This is the dense pigeonhole regime:

Can all these natural PPP problems be solved faster in the dense pigeonhole regime?

Recently, Bhati et al. [3] gave an algorithm for dense Equal Sums instances. For $m$ positive integers bounded by $M$, they obtain $M^{o(1)} \cdot\operatorname{poly}(m)$ time when $m = \omega(\log M)$. Earlier algorithms used the pigeonhole promise to improve the dependence on $m$ [10, 11]. We extend their method to binary collision SIS and obtain an algorithm for weak constrained SIS, whose general form is PWPP-complete [16]. Explicit reductions give algorithms for dense variants of Equal Vector Sums, Minkowski, and Blichfeldt as well.

Our results

Throughout, $n$ is positive, $q \ge2$ is a power of two, and logarithms have base 2. We write $|I|$ for the binary input length. We first study the following collision variant of SIS.

There are $2^m$ binary vectors and only $q^n$ possible images under $A$. Since $m > n \log q$, the pigeonhole principle guarantees a collision. In cryptographic SIS, the matrix is usually sampled at random and larger coordinates may be allowed. Our algorithm works for every input matrix.

Evaluating $A$ on $O(q^n)$ distinct binary vectors and comparing their images finds a collision in time $q^n \cdot\operatorname{poly}(|I|)$. Our main result improves this exponential factor in the dense regime.

When $\delta= \omega(1)$, the running time is $q^{o(n)} \cdot\operatorname{poly}(|I|)$, with subexponential dependence on $n \log q$. In the other regime, our algorithm is even polynomial whenever $n = O((\log m)^2/\log q)$. The same polynomial-time guarantee holds for all the consequences below (using their respective density parameters). To the best of our knowledge, this guarantee was not previously known for any of the variants presented below.

We would like to note that improving the dependence on $\log\delta$ further is unlikely with current techniques: as observed by Bhati et al. [3], any improvements would yield a breakthrough for the Successive Minima Problem (SMP).

We recall the SMP and the proof in § 2.4.

Consequences Weak constrained SIS, introduced in [16], adds linear constraints to binary collision SIS: both output vectors must also satisfy $G\mathbf{x} = G\mathbf{y} = 0$. The matrix $G$ is binary invertible, which allows us to choose some coordinates of the vectors freely and then compute the remaining coordinates uniquely (see Definition 2.1 for a formal definition).

Binary invertibility of $G$ lets us construct valid output vectors $\mathbf{x}$ in the following way: choose $m-d\log q$ coordinates of $\mathbf{x}$ freely. Then, by the design of $G$, each choice uniquely determines the other $d\log q$ coordinates. Thus, exactly $2^{m-d\log q} > q^n$ binary vectors satisfy $G\mathbf{x} = 0$, and two of them must have the same image under $A$. The same argument works with $0$ replaced by any target $\mathbf{b} \in\mathbb{Z}_q^d$.

For parameters satisfying this stronger density condition, the corollary also gives an algorithm for finding collisions in the hash-function family of [16].

Equal Vector Sums replaces the integers in Equal Sums by integer vectors: the two subsets must have the same sum in every coordinate. Such equalities also appear in bounds on the number of nonzero variables needed in integer programs [8]. We assume that every input vector is nonzero, since a zero vector and the empty subset already give equal sums.

For $n = 1$ and positive inputs, this is a dense version of Equal Sums. The following corollary extends the dense scalar algorithm of [3] to several coordinates.

Common elements can be deleted from the two subsets, so, if $A$ has the input vectors as its columns, we obtain a nonzero $\mathbf{z} \in\{-1,0,1\}^{m}$ with $A\mathbf{z} = 0$ over the integers.

Minkowski’s problem asks for a short nonzero lattice vector in the modular lattice $\Lambda_q^{\perp}(A)$ prescribed by a matrix $A$ (we recall basic facts about lattices in § 2.2).

The density promise makes the bound on the infinity norm less than $2$, so the required vector has coordinates in $\{-1,0,1\}$. Minkowski’s theorem is an important tool in mathematics that guarantees a vector satisfying the bound above [12]. Sotiraki et al. [16] showed that its general computational form belongs to PPP. Here we give a subexponential-time algorithm for it in the dense regime.

Blichfeldt’s theorem is a basic tool in the geometry of numbers and gives a standard proof of Minkowski’s theorem [4]. Its general computational form is PPP-complete. Several lattice approximation problems can be solved using a polynomial number of calls to a Blichfeldt solver [16]. We consider the following version for integer points in a box and modular lattices, defined in § 2.2.

Figure 1 shows the reductions and their corollary numbers.

Technical overview

We adapt the block-merging algorithm of [3] to prove Theorem 1.1. For $\delta= O(1)$, brute force gives the required bound. For $\delta= \omega(1)$, we choose the largest power of two $k \ge2$ with $k \le m$ and $k/\log k \le\delta/2$, and put $W := 2^{\lceil\delta n \log q/(2k)\rceil}$. Divide the columns into $k$ blocks $T_0^0,\ldots,T_{k-1}^0$, each of size at least $\lfloor m/k\rfloor$. Each block supplies at least $W$ binary vectors, as follows. For each $i \in[0,k)$, we construct a set $Y_i^0$ of size $W$ by taking any $W$ distinct binary vectors supported on $T_i^0$ and computing $Ax$; this is possible since there are $2^{|T_i^0|} \ge2^{\lfloor m/k\rfloor} > W$ such vectors. A repeated image within a block is already a collision. For every $\mathbf{y} \in Y_i^0$, we store the binary vector $\mathbf{f}(\mathbf{y})$ that produced $\mathbf{y}$. All blocks $T_i^0$ are pairwise disjoint, so different pairs have different merged binary vectors.

Let $\boldsymbol{\mu}^0 = \mathbf{1}_n$ be the vector of $n$ ones. To obtain $\boldsymbol{\mu}^j$, start with $\boldsymbol{\mu}^{j-1}$ and repeat the following step $\log W$ times: multiply a coordinate with the smallest current value by $2$, breaking ties by the smallest index. Throughout this, the entries of $A$ are integers in $[0,q)$, and all products and sums are computed over the integers. See ?? 1.

Algorithm 1: Algorithm behind Theorem 1.1.

1. Partition $[m]$ into $T_0^0 \uplus\cdots\uplus T_{k-1}^0$ as above

2. $Y_i^0 \gets W$ images from $T_i^0$ for every $i \in[0,k)$, and return a collision if found

3. for $j = 1,\ldots,\log k$ and $i = 0,\ldots,k/2^j-1$ do

4. Form all $W^2$ pairs from $Y_{2i}^{j-1}$ and $Y_{2i+1}^{j-1}$

5. Return a collision if two pair sums agree, and let $Z$ be the sums

6. Partition $Z$ into classes $B_p \gets\{z \in Z : z \bmod\mu^j = p\}$

7. $p^\star\gets\arg\max_p |B_p|$

8. $Y_i^j \gets$ any $W$ entries of $B_{p^\star}$

9. end

10. Pick any two elements of $Y_0^{\log k}$ and report a collision between them

Throughout the procedure, we keep the following invariants: (i) all vectors of $Y_i^j$ are pairwise congruent modulo $\mu^j$ and (ii) each $Y_i^j$ has size $W$. For $j = 0$, both conditions are true. For the induction step, the main point is that if we did not find a collision, then $|Z| = |Y_{2i}^{j-1}||Y_{2i+1}^{j-1}| = W^2$. The algorithm partitions $Z$ into at most $W$ disjoint classes, so at least one of them will have size at least $W$.

We claim that this procedure eventually finds a correct collision. Collisions found within the for-loop are obviously correct, so assume no such collision within this loop was found. By the invariants, the set $Y_0^{\log k}$ contains at least two elements. These are congruent modulo $\mu^{\log k}$. Since $W^{\log k} \ge q^n$, this implies that all moduli in $\mu^{\log k}$ are (multiples of) $q$. This in turn means that these two elements of $Y_0^{\log k}$ map to the same value mod $q$, which means they form a collision that can be reported in the final step of the algorithm!

For the running time, observe that each merge takes $W^2 \cdot\operatorname{poly}(|I|)$ time. By the maximality of $k$, we have $W^2 \le4q^{4n/\log\delta}$. Since there are fewer than $m$ merges, this yields the running time in Theorem 1.1. See § 3 for the full proof.

Weak constrained SIS in the dense setting

The reduction for Corollary 1.3 must find a collision whose two vectors also have the prescribed image $\mathbf{b}$ under a binary invertible matrix $G \in\mathbb{Z}_q^{d \times m}$. Informally, the first $d\log q$ columns of $G$ form $d$ blocks of $\log q$ columns: row $i$ has the binary weights $1,2,4,\ldots,2^{\log q-1}$ in block $i$, zeros in earlier blocks, and arbitrary entries in all later columns (see Definition 2.1). For example, for $q = 16$ and $d = 3$, every matrix of the following form is binary invertible:

Each star is an arbitrary element of $\mathbb{Z}_{16}$. The three diagonal blocks encode four binary bits each, and the last column is $G_1$. Split $A = [A_0\ A_1]$ and $G = [G_0\ G_1]$, with the first $d\log q$ columns in $A_0$ and $G_0$.

Apply Theorem 1.1 to the matrix $C = [A_1^{\mathsf{T}},G_1^{\mathsf{T}}]^{\mathsf{T}}$. The resulting binary vectors $\mathbf{z} \ne\mathbf{z}'$ have equal images under both $A_1$ and $G_1$. This equality under $G_1$ is essential: both vectors now require the same residual image $\mathbf{b} - G_1\mathbf{z}$ under $G_0$.

Binary invertibility gives a unique binary vector $\mathbf{u}$ with $G_0\mathbf{u} = \mathbf{b} - G_1\mathbf{z}$. We compute it from the last row to the first, setting each gadget block to the binary decomposition of its residual right-hand side. The same $\mathbf{u}$ completes both vectors, giving $\mathbf{x} = [\mathbf{u}^{\mathsf{T}},\mathbf{z}^{\mathsf{T}}]^{\mathsf{T}}$ and $\mathbf{y} = [\mathbf{u}^{\mathsf{T}},(\mathbf{z}')^{\mathsf{T}}]^{\mathsf{T}}$. They satisfy $G\mathbf{x} = G\mathbf{y} = \mathbf{b}$, and $\mathbf{u}$ cancels in $A\mathbf{x} - A\mathbf{y} = A_1(\mathbf{z} - \mathbf{z}') = 0$. The instance has $n+d$ rows and $m-d\log q$ columns, giving exactly the density and running time in Corollary 1.3. Constructing the instance and completing the vectors take polynomial time.

The other reductions follow the same template: construct a dense SIS instance and convert its collision to the required solution. For integer vector sums, the modulus is large enough to turn a modular equality into an integer equality. For Dense Bichfeldt, binary expansion encodes the box, and Dense Minkowski uses the box $\{0,1\}^m$. § 4 gives the full reductions.

Related work

Sotiraki, Zampetakis, and Zirdelis [16] proved that constrained SIS is PPP-complete and weak constrained SIS is PWPP-complete. Their construction also gives the hash family $\mathcal{H}_{\mathrm{cSIS}}$, whose collision problem is weak constrained SIS. These completeness results depend on the additional constraints in $G$.

For Equal Subset Sum without the pigeonhole promise, successive improvements [13, 15] yield the best known running time of $1.7067^m \cdot\operatorname{poly}(|I|)$ for $m$ inputs.

Under the pigeonhole promise, faster algorithms are known for Equal Sums. Jin and Wu [11] gave a randomized $2^{0.4m}\cdot\operatorname{poly}(|I|)$-time algorithm. Jin, Williams, and Zhang [10] improved it to $2^{m/3}\operatorname{poly}(|I|)$. Bhati et al. [3] obtain $M^{o(1)}\cdot\operatorname{poly}(m)$ time for integers bounded by $M$ when $m=\omega(\log M)$. We extend their block-merging method to modular systems and use their scalar reduction to transfer the conditional lower bound.

A related line of work uses Frobenius-number bounds to obtain faster algorithms for total Unbounded Subset Sum. For distinct positive integers $a_1,\ldots,a_m$ with greatest common divisor $1$, this problem asks for nonnegative integer coefficients $x_i$ such that $\sum_i a_i x_i=b$. Writing $M=\max_i a_i$, Aggarwal, Joux, Santha, and Węgrzycki [1] give a polynomial-time algorithm when $b\geq\varepsilon M^2$ for any fixed $\varepsilon>0$, and analogous results for integer programming with equalities. Chen, Mao, and Zhang [5] subsequently gave an expected $O(m\log M)$-time algorithm when $b\geq CM^2/m$ for a sufficiently large absolute constant $C$, using constructive results from additive combinatorics.

For the modular pigeonhole problem in one row, Allcock et al. [2] give a $\widetilde{O}(2^{m/2})$-time algorithm whenever $q<2^m$. Using only $\log q+1$ columns gives the $q^{1/2}\cdot\operatorname{poly}(|I|)$ bound for one-row SIS. A classical algorithm of Regev, described by Chen, Liu, and Zhandry [6 Appendix A], solves binary collision SIS in polynomial time when $m\geq(n+1)\log q$. Theorem 1.1 gives a subexponential bound already when $m=\omega(n\log q)$.

The number-balancing reductions of Hoberg et al. [9] concern general convex bodies. Corollary 1.5 concerns only the modular lattices $\Lambda_q^\perp(A)$ with $m>n\log q$.

Wagner’s generalized birthday algorithm [17] merges lists while imposing stronger conditions on their partial sums at each level. Ducas, Engelberts, and Loyer [7] use a lattice form of this method and discrete Gaussian sampling to give subexponential algorithms for SIS in the infinity norm. Their guarantees concern random matrices, polynomial prime moduli, and norm bounds larger than one. Our algorithm uses a power-of-two modulus and works for every input matrix. It keeps a largest congruence class at each merge, whose size is bounded below by counting.

Preliminaries

We write $[m]=\{1,\ldots,m\}$, $[a,b]=\{a,\ldots,b\}$, $[a,b)=[a,b-1]$. All logarithms have base 2, and $|I|$ denotes the binary input length. Vectors are column vectors written in bold (e.g., $\mathbf{x}$), with binary vectors additionally underlined (e.g., $\underline{\mathbf{x}}$). We write $[\mathbf{u}^{\mathsf{T}},\mathbf{v}^{\mathsf{T}}]^{\mathsf{T}}$ for their vertical concatenation. Matrix equations over $\mathbb{Z}_q$ are read modulo $q$. Vector congruences and remainders are taken coordinatewise. The vectors $\mathbf{0}$ and $\mathbf{1}_n$ have all coordinates zero and one, respectively. For $B,C\subseteq\mathbb{Z}_q^n$, their sumset is $B+C=\{\mathbf{b}+\mathbf{c}:\mathbf{b}\in B,\ \mathbf{c}\in C\}$.

Total search and pigeonhole classes

A search problem is total if every input has a solution. The class TFNP consists of total search problems whose solutions have size polynomial in input size and that can be verified in polynomial time. A Boolean circuit is a directed acyclic graph with ordered input and output nodes and gates computing $\neg$, $\land$, $\lor$, or $\oplus$. A negation gate has one input and the other gates have two. Evaluating its gates in topological order defines a function $C:\{0,1\}^r\to\{0,1\}^s$, where $r$ and $s$ count the input and output nodes, respectively. Its size $|C|$ is the number of nodes.

The search problem PIGEONHOLE CIRCUIT takes a Boolean circuit $C:\{0,1\}^r\to\{0,1\}^r$ and asks for either an input $\mathbf{x}$ with $C(\mathbf{x})=\mathbf{0}_r$ or distinct inputs $\mathbf{x},\mathbf{y}$ with $C(\mathbf{x})=C(\mathbf{y})$. If no input maps to zero, the $2^r$ inputs have at most $2^r-1$ possible outputs, so a collision exists. The class PPP consists of search problems reducible to PIGEONHOLE CIRCUIT by polynomial-time search reductions [14].

The search problem Collision takes as input a Boolean circuit $C$ with $r$ inputs and $s<r$ outputs and asks for two distinct vectors $\mathbf{x},\mathbf{y}\in\{0,1\}^{r}$ such that $C(\mathbf{x})=C(\mathbf{y})$. There are at least twice as many inputs as possible outputs. The class PWPP consists of search problems reducible to Collision by polynomial-time search reductions [16]. Thus, PWPP $\subseteq$ PPP $\subseteq$ TFNP. A problem is complete for one of these classes if it belongs to the class and every problem in the class reduces to it.

Observe that binary collision SIS (Problem 1) belongs to PWPP. Namely, one can encode $A\mathbf{x}$ in binary to get a circuit with $m$ input bits and $n\log q<m$ output bits. The reductions in § 4 also place Equal Vector Sums, Dense Minkowski, and Dense Blichfeldt in PWPP under their respective input promises.

Equal Sums [14] takes positive integers $a_1,\ldots,a_m$ with $\sum_i a_i<2^{m-1}$ and asks for distinct subsets $S,T\subseteq[m]$ such that $\sum_{i\in S}a_i=\sum_{i\in T}a_i$. Write $M=\max_i a_i$. There are $2^m$ subsets and fewer than $2^m$ possible sums, so a solution exists.

Lattices and their search problems

A full-rank lattice in $\mathbb{R}^{m}$ is a set $\mathcal{L}=D\mathbb{Z}^{m}$, where $D\in\mathbb{R}^{m\times m}$ is nonsingular. Its columns form a basis of $\mathcal{L}$, and its determinant is $\det(\mathcal{L})=\lvert\det D\rvert$. For computational problems, bases have rational entries and are encoded in binary. We use the infinity norm $\lVert\mathbf{v}\rVert_{\infty}=\max_i\lvert v_i\rvert$ and the Euclidean norm $\lVert\mathbf{v}\rVert_2=(\sum_i v_i^2)^{1/2}$.

A lattice coset is a translate $\mathbf{p}+\mathcal{L}=\{\mathbf{p}+\mathbf{v}:\mathbf{v}\in\mathcal{L}\}$. Two points $\mathbf{x},\mathbf{y}$ lie in the same coset exactly when $\mathbf{x}-\mathbf{y}\in\mathcal{L}$. If $\mathcal{L}\subseteq\mathbb{Z}^{m}$ is a full-rank integer lattice, then $\det(\mathcal{L})$ equals the number of its cosets in $\mathbb{Z}^{m}$.

For $A\in\mathbb{Z}_{q}^{n\times m}$, we use the modular lattice $\Lambda_q^{\perp}(A)=\{\mathbf{z}\in\mathbb{Z}^{m}:A\mathbf{z}=0\pmod q\}$. It contains $q\mathbb{Z}^{m}$ and therefore has full rank. Two integer vectors lie in the same coset of $\Lambda_q^{\perp}(A)$ exactly when they have the same image under $A$. Since there are at most $q^n$ images, we have $1\leq\det(\Lambda_q^{\perp}(A))\leq q^n$.

Minkowski’s theorem [12] guarantees that every full-rank lattice $\mathcal{L}\subseteq\mathbb{R}^{m}$ contains a nonzero vector $\mathbf{v}$ with $\lVert\mathbf{v}\rVert_{\infty}\leq\det(\mathcal{L})^{1/m}$. Minkowski’s problem asks for such a vector given a lattice basis. Notice that Problem 4 restricts the input to modular lattices with $m>n\log q$.

Blichfeldt’s theorem [4] states that a measurable set $S\subseteq\mathbb{R}^{m}$ of volume greater than $\det(\mathcal{L})$ contains distinct points $\mathbf{x},\mathbf{y}$ with $\mathbf{x}-\mathbf{y}\in\mathcal{L}$. For integer points, the counting argument is enough: any set $S\subseteq\mathbb{Z}^{m}$ with $\lvert S\rvert>\det(\mathcal{L})$ contains two points in the same coset of a full-rank integer lattice $\mathcal{L}$. This guarantees a solution to Dense Blichfeldt (Problem 5). The more general computational formulations of Minkowski and Blichfeldt are studied in [16].

Binary invertibility and weak constrained SIS

For a power-of-two $q\geq2$, the gadget vector is the column $\boldsymbol{\gamma}_q=(2^0,2^1,\ldots,2^{\log q-1})^{\mathsf{T}}$. For $a\in\mathbb{Z}_q$, let $\operatorname{bin}(a)\in\{0,1\}^{\log q}$ be the binary decomposition of its representative in $\{0,\ldots,q-1\}$, with the least significant bit first. Thus, $\boldsymbol{\gamma}_q^{\mathsf{T}}\operatorname{bin}(a)=a\pmod q$. For vectors, $\operatorname{bin}$ concatenates the decompositions of successive coordinates.

In words, divide the first $d\log q$ columns into $d$ blocks. Row $i$ contains the binary weights $1,2,4,\ldots,2^{\log q-1}$ in block $i$, zeros in earlier blocks, and arbitrary entries in later columns. For every $\mathbf{z}\in\{0,1\}^{m-d\log q}$ and target $\mathbf{b}\in\mathbb{Z}_q^d$, there is a unique $\mathbf{u}\in\{0,1\}^{d\log q}$ such that $G[\mathbf{u}^{\mathsf{T}},\mathbf{z}^{\mathsf{T}}]^{\mathsf{T}}=\mathbf{b}$.

To compute $\mathbf{u}$, process rows $i=d,d-1,\ldots,1$. Subtract the contribution of the already chosen coordinates from $\mathbf{b}_i$ modulo $q, and write this remainder in binary to fill block $i$. This is the only choice satisfying row $i$, and it does not affect the rows already processed. Thus, the procedure gives the unique $\mathbf{u}$. After computing $V\mathbf{z}$, it uses $O(d^2\log q)$ modular arithmetic operations.

A standard brute-force algorithm gives the following bound.

Proof. Since $2^{m-d\log q}>q^n$, choose $q^n+1$ distinct binary vectors of length $m-d\log q$. Complete each vector to a binary vector $\mathbf{x}$ with $G\mathbf{x}=\mathbf{b}$ using the procedure above. The completed vectors are distinct and their images under $A$ lie in $\mathbb{Z}_q^n$, so two images coincide. Completing the vectors, evaluating $A$, and sorting the images to find a repetition take $q^n\cdot\operatorname{poly}(|I|)$ total time.

The lattice hypothesis and lower bound

Bhati et al. [3 Section 5] give a conditional lower bound for Equal Sums. For a full-rank lattice $\mathcal{L}\subseteq\mathbb{R}^N$, $\lambda_N(\mathcal{L})$ is the least radius of a Euclidean ball centered at $0$ containing $N$ linearly independent lattice vectors. The hypothesis concerns the $N$-th Successive Minima Problem, which asks for one nonzero vector of length at most a given multiple of $\lambda_N(\mathcal{L})$. It states that, for every constant $c\geq1$, there is an $\varepsilon>0$ such that no $O(2^{\varepsilon N})$-time algorithm, given $\mathcal{L}$, returns with high probability a nonzero $\mathbf{v}\in\mathcal{L}$ with $\lVert\mathbf{v}\rVert_2\leq O(N^c)\lambda_N(\mathcal{L})$. Here and below, the running times include a polynomial factor in the binary encoding length of the lattice basis.

Lemma 1.2 (cf. [3]). Any algorithm that solves binary collision SIS in time $q^{o(n/\log\delta)}\cdot\operatorname{poly}(|I|)$ would improve the best known algorithms for SMP, even when $\delta=\operatorname{poly}(|I|)$ and $n=O(1)$.

Proof. Recall that Bhati et al. [3 Section 5] rule out a $M^{o(1/\log m)}\cdot\operatorname{poly}(m)$-time algorithm for Equal Sums. Their reduction gives hard instances with $m$ positive integers bounded by $M=2^{\Theta(\sqrt{m}\log m)}$. Choosing the smallest power of two $q>mM$ gives $mM<q\leq2mM$. Form the binary collision SIS instance $A=[a_1,\ldots,a_m]\in\mathbb{Z}_q^n$. All subset sums lie in $[0,q)$, so a modular collision $A\mathbf{x}=A\mathbf{y}$ gives distinct subsets $S=\{i:x_i=1\}$ and $T=\{i:y_i=1\}$ with equal integer sums. The instance has $n=1$, $\log q=\Theta(\log M)$, and $\delta=m/\log q=\Theta(\sqrt{m}/\log m)=m^{1/2+o(1)}$. In particular, $\delta>1$ for sufficiently large $m$, so this is a valid binary collision SIS instance. The reduction takes polynomial time, so a binary collision SIS algorithm with running time $q^{o(1/\log\delta)}\cdot\operatorname{poly}(|I|)$ would solve Equal Sums in time $M^{o(1/\log m)}\cdot\operatorname{poly}(m)$.

Main proof

Theorem 1.1. An instance $I$ of binary collision SIS (Problem 1) with parameters $n$, $q$, and $\delta$ can be solved deterministically in time $q^{O(n/\log\delta)}\cdot\operatorname{poly}(|I|)$.

Proof. If $\delta\leq4$, we can find such distinct $\mathbf{x},\mathbf{y}$ by brute force in time $q^{O(n)}\cdot\operatorname{poly}(|I|)$. Henceforth assume $\delta>4$. Let $k\geq2$ be the largest integer power of $2$ such that $k/\log k\leq\delta/2$ and $k\leq m$.

For $j\in[0,\log k]$ define a family $T^j=\{T_i^j:i\in[0,k/2^j)\}$ of integer subintervals of $[m]$:

and the families of Boolean indicator vectors of the subsets of $T_i^j$:

Note that for $j\in[\log k]$ we have

Moreover, each $T_i^j$ has size at least $2^j\cdot\left\lfloor\frac{m}{k}\right\rfloor$. Finally, let $W:=2^{\lceil\delta n\log q/(2k)\rceil}$.

Claim 3.1. $W\leq2^{\lfloor m/k\rfloor}$.

Proof. We have $\log W=\lceil\delta n\log q/(2k)\rceil=\lceil m/(2k)\rceil\leq\lfloor m/k\rfloor$, where the inequality holds since $m/k\geq1$.

In particular, each set $X_i^0$ has size at least $2^{\lfloor m/k\rfloor}\geq W$.

We now present the algorithm. In the entire routine, we regard the input (the entries of $A$) as integers in $[0,q)$ instead of remainders mod $q$, and all products and sums in this proof are computed over the integers.

We begin by initializing the integer vector $\mu^0 = \mathbf{1}_n$. Next, for each $i \in[0,k)$ we build a set $Y_i^0$ of size $W$ by taking any $W$ vectors $\mathbf{x} \in X_i^0$ and adding $A\mathbf{x}$ to $Y_i^0$. If, during this step, we come across two vectors $\mathbf{x}^1,\mathbf{x}^2$ such that $A\mathbf{x}^1 = A\mathbf{x}^2$, we declare success immediately with $(\mathbf{x}^1,\mathbf{x}^2)$ as the sought collision. Otherwise, create an explicit mapping from the entries of $Y_i^0$ to the binary vectors of $X_i^0$ and call it $f$. That is, for every $\mathbf{y} \in Y_i^0$ write $f(\mathbf{y})$ to refer to the vector $\mathbf{x} \in X_i^0$ with $A\mathbf{x} = \mathbf{y}$ that produced $\mathbf{y}$. We stress that here $f$ is understood separately for each set $Y_i^0$.

Now the algorithm proceeds in $\log k$ rounds, indexed by $j = 1,\ldots,\log k$. On the $j$th round:

1. Construct a vector $\mu^j$ from $\mu^{j-1}$ by performing $\log W$ coordinate doublings, every time selecting a coordinate with the smallest value, breaking ties by the smallest index.

2. For each $i \in\left[0,\frac{k}{2^j}\right)$:

   • Compute $Z := \{\mathbf{y}^1+\mathbf{y}^2 : \mathbf{y}^1 \in Y_{2i}^{j-1},\mathbf{y}^2 \in Y_{2i+1}^{j-1}\}$. If we spot a collision, i.e., we find two different pairs of vectors $(\mathbf{y}^1,\mathbf{y}^2),((\mathbf{y}^1)',(\mathbf{y}^2)')$ with $\mathbf{y}^1+\mathbf{y}^2 = (\mathbf{y}^1)'+(\mathbf{y}^2)'$, we immediately terminate and return the collision $f(\mathbf{y}^1)+f(\mathbf{y}^2), f((\mathbf{y}^1)')+f((\mathbf{y}^2)')$. Otherwise, for each $\mathbf{z}=\mathbf{y}^1+\mathbf{y}^2$, we define the mapping $f(\mathbf{z})=f(\mathbf{y}^1)+f(\mathbf{y}^2)$.

   • Create the partition $\mathcal{P}$ of $Z$ into subsets based on the congruence classes of the vectors in $Z$ modulo $\mu^j$; that is, for each $\mathbf{y},\mathbf{y}'$ in the same part, we have $\mathbf{y}\equiv\mathbf{y}'\pmod{\mu^j}$.

   • Choose any set $P\in\mathcal{P}$ of largest size and let $Y_i^j\subseteq P$ be an arbitrary set of $W$ vectors.

Correctness. It is straightforward to see that throughout the algorithm the following invariants are preserved for every $j\in[0,\log k]$ and $i\in\left[0,\frac{k}{2^j}\right)$:

• each $Y_i^j$ has size $W$;

• for each $\mathbf{y},\mathbf{y}'\in Y_i^j$, we have $\mathbf{y}\equiv\mathbf{y}'\pmod{\mu^j}$;

• for each $\mathbf{y}\in Y_i^j$, we have $A f(\mathbf{y})=\mathbf{y}$ and $f(\mathbf{y})\in X_i^j$;

• $\prod_{\ell\in[n]}\mu_\ell^j=2^{\log W\cdot j}$; each $\mu_\ell^j$ is a power of $2$, and for every $\ell,\ell'$, we have $\mu_\ell^j\le2\mu_{\ell'}^j$.

Now consider a round $j\in[\log k]$ and an index $i\in\left[0,\frac{k}{2^j}\right)$. If a collision is spotted, the output is correct by the invariants above; so assume otherwise. First, the size of the partition $\mathcal{P}$ is at most $W$: indeed, by the invariant in round $j-1$, all vectors of $Y_{2i}^{j-1}$ are pairwise congruent to each other modulo $\mu^{j-1}$, and the same holds for $Y_{2i+1}^{j-1}$. Hence, all vectors of $Z$ are also pairwise congruent to each other modulo $\mu^{j-1}$. $\mathcal{P}$ partitions these vectors into congruence classes modulo $\mu^j$; hence there are at most

congruence classes, and so $|\mathcal{P}|\le W$. Then, since $|Z|=|Y_{2i}^{j-1}|\cdot|Y_{2i+1}^{j-1}|=W^2$, we conclude that some part $P\in\mathcal{P}$ has size at least $W$, as required.

Suppose the algorithm finished without reporting a collision, and consider the set $Y_0^{\log k}$. All vectors therein are pairwise congruent modulo $\mu^{\log k}$. We have

where the last inequality follows from the definition of $k$ such that $k/\log k\le\delta/2$. Thus, all coordinates of $\mu^{\log k}$ are at least $q$: since $q$ is a power of two, any coordinate smaller than $q$ would need to be upper-bounded by $q/2$. But then the invariant would guarantee that all the remaining coordinates would be upper-bounded by $q$. Then the product of all entries of $\mu^{\log k}$ would not exceed $q^n/2$—a contradiction. Therefore, all coordinates of $\mu^{\log k}$ are actually divisible by $q$. Now take any two distinct vectors $\mathbf{y},\mathbf{y}'\in Y_0^{\log k}$. We have $\mathbf{y}\equiv\mathbf{y}'\pmod{\mu^{\log k}}$, and so $\mathbf{y}\equiv\mathbf{y}'\pmod{q\cdot\mathbf{1}_n}$. Then the corresponding binary vectors $\mathbf{x}=f(\mathbf{y}),\mathbf{x}'=f(\mathbf{y}')$ yield a collision pair $(\mathbf{x},\mathbf{x}')\pmod q$, which we can return from the algorithm. Time analysis. On initialization, we compute all sets $Y_i^0$ for $i \in[0,k)$ in total time $\mathcal{O}(k \cdot W \cdot\frac{m}{k} \cdot n)=W\cdot\operatorname{poly}(|I|)$: we have $|Y_i^0|=W$, and each element of $Y_i^0$ is formed by multiplying a vector of $X_i^0$—with at most $\frac{m}{k}$ non-zero entries—by $A$. Now we analyze the time spent on the $j$th round. Fix an iteration $i \in[0,\frac{j}{2})$. Each set $Y_i^j$ has size $W$. The set $Z$ has size $\mathcal{O}(W^2)$, so computing $Z$ and partitioning it take $W^2\cdot\operatorname{poly}(|I|)$ time. Finding the largest $P \in\mathcal{P}$ requires $\mathcal{O}(W)$ time. Therefore, the $j$th round requires $W^2\cdot\operatorname{poly}(|I|)$ time, so the total running time of the algorithm is

The last polynomial factor absorbs the constant from rounding. As we have chosen $k\ge2$ to be the largest power of 2 such that $k\le m$ and $2k\le\delta\log k$, one of the following must hold:

• $2k>m$. Then $q^{\delta n/k}=2^{\delta n\log q/k}=2^{m/k}\le4$, so $q^{\delta n/k}\cdot\operatorname{poly}(|I|)=\operatorname{poly}(|I|)$.

• $4k>\delta\log(2k)$. Then $\delta n/k<4n/\log(2k)<4n/\log\delta$, with the second inequality following from $4k>\delta\log(2k)\ge2\delta$. Hence, $q^{\delta n/k}\cdot\operatorname{poly}(|I|)=q^{O(n/\log\delta)}\cdot\operatorname{poly}(|I|)$.

The required time bounds follow. $\square$

Reductions and proofs of the corollaries

Each proof in this section constructs an instance of another problem in polynomial time and converts every solution back to the original instance. Dense Minkowski reduces to Dense Blichfeldt, which reduces to binary collision SIS. The other two reductions go directly to binary collision SIS. Figure 1 shows these reductions.

We have $\mathbf{v} = 0 \pmod q$ and $\lVert\mathbf{v}\rVert_{\infty} \le\sum_i |x_i-y_i|\lVert\mathbf{a}_i\rVert_{\infty} \le m\Delta< q$. Each coordinate of $\mathbf{v}$ is a multiple of $q$ of absolute value less than $q$, so $\mathbf{v} = 0$ over the integers. Common elements may be removed from $S$ and $T$ if disjoint subsets are desired.

Since $q \le2m\Delta$, we have $\log q = O(\log m + \log\Delta)$ and so the bit length of the reduced instance, $O(nm\log q)$, is polynomial in $|I|$. Constructing $A$ and decoding $S,T$ take polynomial time in the input length, so Theorem 1.1 gives the stated $q^{O(n/\log\delta)}\cdot\operatorname{poly}(|I|)$ bound.

Proof. Given a Dense Blichfeldt instance (Problem 5), write $A=[a_1\ \cdots\ a_m]$ and let $C\in\mathbb{Z}^{n\times\log|B|}$ be the matrix with columns $c_{i,j}=2^j a_i\pmod q$ for $i\in[m]$ and $0\le j<\log L_i$. Since $\log|B|>n\log q$, this is a valid binary collision SIS instance with density $\log|B|/(n\log q)=\delta$. For a binary vector $\mathbf{u}$ with these coordinates, define $\phi(\mathbf{u})\in\mathbb{Z}^m$ by

Binary expansion gives a bijection from $\{0,1\}^{\log|B|}$ to $\prod_i\{0,\ldots,L_i-1\}=B-p$. We have $C\mathbf{u}=A\phi(\mathbf{u})\pmod q$. Given a solution $\mathbf{u}\ne\mathbf{u}'$ with $C\mathbf{u}=C\mathbf{u}'$, return $\mathbf{x}=\mathbf{p}+\phi(\mathbf{u})$ and $\mathbf{y}=\mathbf{p}+\phi(\mathbf{u}')$. The bijection gives distinct points in $B$, and

Hence $\mathbf{x}-\mathbf{y}\in\Lambda_q^\perp(A)$, as required.

For the running-time analysis, the constructed matrix has $n\log|B|$ entries of $\log q$ bits, and its columns can be computed by successive doublings modulo $q$. Also, decoding the vectors and adding $\mathbf{p}$ take polynomial time. So if we apply Theorem 1.1 with $n$ rows and $\log|B|$ columns, we obtain an algorithm running in time $q^{O(n/\log\delta)}\cdot\operatorname{poly}(|I|)$.

Proof. We reduce Dense Minkowski (Problem 4) to Dense Blichfeldt (Problem 5). Keep $A$ and $q$, set $\mathbf{p}=0$, and set $L_i=2$ for every $i\in[m]$, so the box is $B=\{0,1\}^m$. The constructed Dense Blichfeldt instance is valid because $\log|B|/(n\log q)>1$ since $m>n\log q$.

Given a solution $\mathbf{x}\ne\mathbf{y}$ for this box, return $\mathbf{z}=\mathbf{x}-\mathbf{y}$. Then $\mathbf{z}\in\Lambda_q^\perp(A)$ is nonzero and $\mathbf{z}\in\{-1,0,1\}^m$, so $\lVert\mathbf{z}\rVert_\infty=1$. Since $\Lambda_q^\perp(A)$ is a full-rank sublattice of $\mathbb{Z}^m$, its determinant is a positive integer, hence at least $1$. Thus $\lVert\mathbf{z}\rVert_\infty=1\le\det(\Lambda_q^\perp(A))^{1/m}$, which is Minkowski’s required bound. Every nonzero vector of this integer lattice has infinity norm at least $1$, so $\mathbf{z}$ is also shortest.

The instance can be constructed in polynomial time. Applying Corollary 1.6 with the same $n$, $q$, and $\delta$ yields the required $q^{O(n/\log\delta)}\cdot\operatorname{poly}(|I|)$ time.

Use of generative AI

We used OpenAI Codex and GPT-6 to proofread and lightly edit the manuscript (for example, to draw Fig. 1). All the ideas and proofs in this paper were developed by humans on whiteboards.