NTRU ⇒ PKE

Standard model · heuristic candidate · HPS98

Statement

HPS98 build PKE over $R=\mathbb{Z}[x]/(x^n-1)$: the public key is $h=g\cdot f^{-1}\mathrm{mod}q$ for short secret $f,g$, and $m$ encrypts to $c=p\cdot r\cdot h+m\mathrm{mod}q$ for short random $r$. HPS98 give no security reduction: key recovery from $h$ is the NTRU problem, and message recovery is a separate closest-vector problem.

Sketch

Decryption computes $f\cdot c=p\cdot r\cdot g+f\cdot m\mathrm{mod}q$, which for suitable parameters holds exactly over $R$ because every factor is short; reducing modulo $p$ leaves $f\cdot m$, and multiplying by $f^{-1}\mathrm{mod}p$ recovers $m$.

Notes

• The unpadded scheme is not IND-CPA: HPS98 sample $g$ with equally many coefficients $+1$ and $-1$, so $g(1)=0$ forces $h(1)=0$, hence $c(1)\equiv m(1)(\mathrm{mod}q)$ — folklore.
• With discrete-Gaussian secret keys over $\mathbb{Z}[x]/(x^n+1)$ the public key is statistically close to uniform, and the modified NTRUEncrypt is IND-CPA under Ring LWE — SS11 (Ring LWE ⇒ PKE (NTRUEncrypt with Gaussian keys)).