Sub-exponential LWE ⇒ CPA-secure PKE
Statement
If LWE is sub-exponentially hard, then Regev’s scheme with , a prime , discrete Gaussian noise of width and samples for a constant is an IND-CPA-secure PKE for one-bit messages. These parameters have , a prime , for , and , so sub-exponential hardness gives a constant such that every efficient adversary, having size at most for all large , distinguishes the LWE samples from uniform with advantage at most , which is negligible — standard. For every , an efficient adversary distinguishing encryptions of and gives an efficient distinguisher between the LWE samples of the public key and uniform — Reg05. That reduction does not use the noise distribution, so it applies at these parameters, at which the scheme is also correct except with negligible probability — standard.