Succinct LWE ⇒ LWE

Fully-black-box reduction · standard model · folklore · security loss: additive in the statistical distance of $\mathrm{TrapGen}$‘s $\mathbf{B}$ from uniform

Statement

For every $\ell$, if $\ell$-succinct LWE is hard for $(n,q,\chi ,m)$, then LWE is hard for the same $(n,q,\chi ,m)$ — folklore.

Sketch

On a succinct-LWE challenge $(\mathbf{B},\mathbf{W},T,{\mathbf{u}}_b)$, run the LWE distinguisher on $({\mathbf{B}}^{\top },{\mathbf{u}}_b^{\top })$ and output its guess, ignoring $(\mathbf{W},T)$. The $\mathbf{B}$ output by $\mathrm{TrapGen}$ is statistically close to uniform, so the only loss is additive in that statistical distance.

Notes

• For $\ell =1$ the converse holds, since $(\mathbf{W},T)$ can be sampled from a uniform $\mathbf{B}$ using a trapdoor for $\mathbf{W}$ alone; for $\ell >1$ no reduction from LWE is known — folklore.