SIS ∈ PWPP

Inclusion · SZZ18 · security loss: none: one Karp reduction to Weak Pigeon, and a collision maps to a solution by subtraction

Statement

For $m\ge n\log q+1$ and $\sqrt{m}\le \beta <q$, worst-case SIS for $(n,m,q,\beta )$ lies in PWPP — standard. SZZ18 prove more: weak constrained SIS, a binary collision problem whose unconstrained case is the collision form of SIS, is PWPP-complete, and constrained SIS is PPP-complete.

Sketch

Map $\mathbf{A}\in {\mathbb{Z}}_q^{n\times m}$ to the circuit $\{0,1{\}}^m\to \{0,1{\}}^{m-1}$ that sends $\mathbf{x}$ to $\mathbf{Ax}\mathrm{mod}q$, encoded in $\lceil n\log q\rceil \le m-1$ bits and padded. A collision $\mathbf{x}\ne {\mathbf{x}}^{\prime }$ gives $\mathbf{z}=\mathbf{x}-{\mathbf{x}}^{\prime }\in \{-1,0,1{\}}^m\setminus \{0\}$ with $\mathbf{Az}\equiv 0(\mathrm{mod}q)$ and $\Vert \mathbf{z}\Vert \le \sqrt{m}\le \beta$.

Notes

• For $n\log q<m<n\log q+1$ the map need not save a bit, but SIS still lies in PPP: shifted by one, the index of $\mathbf{Ax}$ in ${\mathbb{Z}}_q^n$ is a nonzero element of $\{0,1{\}}^m$ because $q^n<2^m$, so every solution of the resulting Pigeon instance is a collision — standard. When $m-n\log q\ge 1/\mathrm{poly}(n)$, the $k$-fold map $({\mathbf{x}}_1,\dots ,{\mathbf{x}}_k)\mapsto (\mathbf{A}{\mathbf{x}}_1,\dots ,\mathbf{A}{\mathbf{x}}_k)$ with $k=\lceil 1/(m-n\log q)\rceil$ saves a bit, and a collision in it is a collision in some coordinate, so SIS lies in PWPP there too — folklore.
• Membership does not make SIS PWPP-hard; completeness holds for the constrained variants — SZZ18.