Post Quantum Cryptography: NTRU

Preliminary

Parameters

First, we begin by fixing an integer $N \ge 1$ and two moduli $p$ and $q$, and we let $R, R_p$, and $R_q$ be the convolution polynomial rings

$$R=\frac{\mathbb{Z}[x]}{\left(x^N-1\right)}, \quad R_p=\frac{(\mathbb{Z} / p \mathbb{Z})[x]}{\left(x^N-1\right)}, \quad R_q=\frac{(\mathbb{Z} / q \mathbb{Z})[x]}{\left(x^N-1\right)}$$

As usual, we may view a polynomial $\boldsymbol{a}(x) \in R$ as an element of $R_p$ or $R_q$ by reducing its coefficients modulo $p$ or $q$. In the other direction, we use center-lifts to move elements from $R_p$ or $R_q$ to $R$. We make various assumptions on the parameters $N, p$ and $q$, in particular we require that $N$ be prime and that $\operatorname{gcd}(N, q)=\operatorname{gcd}(p, q)=1$.

Ternary Polynomial

For any positive integers $d_1$ and $d_2$, we let

$$\mathcal{T}\left(d_1, d_2\right)=\left\{\begin{aligned} &\boldsymbol{a}(x) \text { has } d_1 \text { coefficients equal to } 1, \\ \boldsymbol{a}(x) \in R:\quad &\boldsymbol{a}(x) \text { has } d_2 \text { coefficients equal to }-1, \\ &\boldsymbol{a}(x) \text { has all other coefficients equal to } 0 \end{aligned}\right\} .$$

Polynomials in $\mathcal{T}\left(d_1, d_2\right)$ are called ternary (or trinary) polynomials. They are analogous to binary polynomials, which have only 0’s and 1’s as coefficients.

NTRU Encryption

We are now ready to describe NTRUEncrypt. Alice (or some trusted authority) chooses public parameters ( $N, p, q, d$ ) satisfying: (1) $\gcd(p,q)=\gcd(N,q)=1$;(2)$q>(6d+1)p$ . Alice’s private key consists of two randomly chosen polynomials

$$\boldsymbol{f}(x) \in \mathcal{T}(d+1, d) \quad \text { and } \quad \boldsymbol{g}(x) \in \mathcal{T}(d, d)$$

Alice computes the inverses

$$\boldsymbol{F}_q(x)=\boldsymbol{f}(x)^{-1} \quad \text { in } R_q \quad \text { and } \quad \boldsymbol{F}_p(x)=\boldsymbol{f}(x)^{-1} \quad \text { in } R_p .$$

Alice next computes

$$\boldsymbol{h}(x)=\boldsymbol{F}_q(x) \star \boldsymbol{g}(x) \quad \text { in } R_q .$$

The polynomial $\boldsymbol{h}(x)$ is Alice’s public key. Her private key, which she’ll need to decrypt messages, is the pair $\left(\boldsymbol{f}(x), \boldsymbol{F}_p(x)\right)$. Alternatively, Alice can just store $\boldsymbol{f}(x)$ and recompute $\boldsymbol{F}_p(x)$ when she needs it.

Bob’s plaintext is a polynomial $\boldsymbol{m}(x) \in R$ whose coefficients satisfy $-\frac{1}{2} p<$ $m_i \leq \frac{1}{2} p$, i.e., the plaintext $\boldsymbol{m}$ is a polynomial in $R$ that is the center-lift of a polynomial in $R_p$. Bob chooses a random polynomial (a random element) $\boldsymbol{r}(x) \in \mathcal{T}(d, d)$ and computes

$$\boldsymbol{e}(x) \equiv p \boldsymbol{h}(x) \star \boldsymbol{r}(x)+\boldsymbol{m}(x) \quad(\bmod q)$$

Bob’s ciphertext $\boldsymbol{e}(x)$ is in the ring $R_q$.
On receiving Bob’s ciphertext, Alice starts the decryption process by computing

$$\boldsymbol{a}(x) \equiv \boldsymbol{f}(x) \star \boldsymbol{e}(x) \quad(\bmod q) .$$

She then center lifts $\boldsymbol{a}(x)$ to an element of $R$ and does a $\bmod p$ computation,

$$\boldsymbol{b}(x) \equiv \boldsymbol{F}_p(x) \star \boldsymbol{a}(x) \quad(\bmod p) .$$

Assuming that the parameters have been chosen properly, we now verify that the polynomial $\boldsymbol{b}(x)$ is equal to the plaintext $\boldsymbol{m}(x)$.

NTRUEncrypt: the NTRU public key cryptosystem

References

[1] Hoffstein J, Pipher J, Silverman J H, et al. An Introduction to Cryptography[M]. Springer New York, 2014.

[2] https://0xffff.one/d/1424/5