Decision LWE ⇒ LWE

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

Hardness of decision LWE in its prime-modulus regime, a prime with Gaussian error of width and for every , is hardness of LWE for the same , since is -computable and , with the same advantage — folklore.