Sub-exponential LWE ⇒ CPA-secure PKE

Fully-black-box reduction · standard model · via leftover hash lemma · Reg05 · security loss: tight up to a factor 2: one run of the CPA adversary on the LWE samples as public key, whose advantage is at most twice the LWE advantage plus a statistical leftover-hash term

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.