Ring LWE ⇒ PKE (NTRUEncrypt with Gaussian keys)

Standard model · SS11 · security loss: tight up to a factor 2: one run of the CPA adversary on one Ring LWE sample, whose advantage is at most twice the Ring LWE advantage plus twice the statistical distance of the public key from uniform

Statement

Let $R=\mathbb{Z}[x]/(x^n+1)$ with $n$ a power of two, and $q$ a prime modulo which $x^n+1$ splits into linear factors. If the NTRU secrets are $g$ and $f=p{f}^{\prime }+1$, with $f^{\prime }$ and $g$ sampled from a discrete Gaussian over $R$ of parameter $\sigma \ge \mathrm{poly}(n)\cdot q^{1/2+\epsilon }$, conditioned on $f$ and $g$ being invertible modulo $q$, then the public key $h=pg{f}^{-1}\mathrm{mod}q$ is statistically close to uniform over $R_q^{\times }$, and the resulting NTRUEncrypt variant is an IND-CPA-secure PKE if Ring LWE over $R_q$ is hard — SS11.

Sketch

Above the smoothing parameter of the relevant lattice the ratio $g{f}^{-1}$ is statistically close to uniform on $R_q^{\times }$, so $h$ may be replaced by $pa$ for the first component $a$ of a Ring LWE sample $(a,as+e)$; then $p(as+e)+M$ is exactly an encryption of $M$, so an IND-CPA adversary against the modified scheme distinguishes $(a,as+e)$ from uniform.

Notes

• The theorem concerns the encryption scheme: SS11 do not reduce Ring LWE to the NTRU key-recovery problem, and the result does not cover the sparse ternary keys of deployed NTRU — SS11.