LWE with polynomial ratio ⇒ SIS

Fully-black-box reduction · standard model · folklore · security loss: Constant factor: ${\mathbf{Adv}}^{\mathrm{lwe}}\ge 0.4\cdot {\mathbf{Adv}}^{\mathrm{sis}}$ for prime $q\ge 75$, with one call to the SIS solver.

Statement

Let $q$ be prime, $\chi$ the discrete Gaussian over $\mathbb{Z}$ of width $\alpha q$, and $\beta \le 1/(4\alpha )$ with $\beta <q$. If decision LWE is hard for $(n,q,\chi ,m)$, then SIS is hard for $(n,m,q,\beta )$, with a constant-factor loss — folklore. Under LWE with polynomial modulus-to-noise ratio this gives SIS in the regime $m>n\log q$, $\sqrt{m}\le \beta <q$: take $\alpha =1/n$, a prime $q\in [2n^{1.5},4n^{1.5}]$ (so $\alpha q\ge 2\sqrt{n}$), $m=\lceil 3n\log q\rceil$ and $\beta =\sqrt{m}$, which is at most $n/4=1/(4\alpha )$ for all large $n$; more generally $\alpha =n^{-c}$ with $\sqrt{m}\le \beta \le n^c/4$.

Sketch

Given $(\mathbf{A},\mathbf{u})$ with $\mathbf{A}\in {\mathbb{Z}}_q^{m\times n}$, run the SIS solver on ${\mathbf{A}}^{\top }$, which is uniform in ${\mathbb{Z}}_q^{n\times m}$, and output “LWE” iff it returns $\mathbf{z}$ with ${\mathbf{A}}^{\top }\mathbf{z}\equiv 0$, $0<\Vert \mathbf{z}\Vert \le \beta$ and $⟨\mathbf{z},\mathbf{u}⟩\mathrm{mod}q\in (-q/4,q/4)$. For $\mathbf{u}=\mathbf{As}+\mathbf{e}$, $⟨\mathbf{z},\mathbf{u}⟩\equiv ⟨\mathbf{z},\mathbf{e}⟩$ is subgaussian with parameter $\Vert \mathbf{z}\Vert \alpha q\le q/4$, so it leaves $(-q/4,q/4)$ with probability at most $2e^{-\pi }<0.09$; for uniform $\mathbf{u}$ it is uniform modulo $q$, since $\mathbf{z}\not\equiv 0$ and $q$ is prime, and lands in the interval with probability at most $1/2+1/q$.

Notes

• Composed with SIS ⇒ CRHF at the same $(n,m,q,\beta )$, LWE with polynomial modulus-to-noise ratio gives collision-resistant hashing keyed by a uniform matrix — standard.