# NTRUEncrypt
## Introduction
- NTRU is an public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures.
- NTRU is a lattice-based algorithm since it relies on mathematical structures called lattices for encryption and decryption. Specifically, NTRU uses a truncated polynomial ring, and the coefficients of polynomials within this ring can be represented as vectors in a lattice. The security of NTRU is based on the difficulty of solving certain problems within these lattices, such as the Shortest Vector Problem (SVP).
## Public Parameters
- **Public Parameters**: $N$, $p$, $q$, $d$
- **Rings**: $R: \frac{\mathbb{Z}[x]}{(x^N-1)}$, $R_q: \frac{\mathbb{Z_q}[x]}{(x^N-1)}$, $R_p:\frac{\mathbb{Z}_p[x]}{(x^N-1)}$
- $N$ is prime.
- $p$ is used to be 3 and is prime.
- $q$ is used to be $2^N > (6d+1)\cdot p$
- $\rm{gcd}(N, q) = \rm{gcd}(p, q) = 1$

## Ecnryption
- **Private keys**: Ternary polynomials $\mathcal{T}(d_1, d_2)$
- $f(x) \in \mathcal{T}(d+1, d)$
- $g(x) \in \mathcal{T}(d, d)$
- $F_q(x) = f(x)^{-1}\ \text{in }R_q$
- $F_p(x) = f(x)^{-1}\ \text{in }R_p$
- **Public key**
- $h(x) = F_q(x)·g(x) = f(x)^{-1}·g(x) \ \text{in } R_q$
- **Plaintext**
- $m(x)\in R$, whose coefficients are in $(-\frac{1}{2}p, \frac{1}{2}p\ ]$
- **Random polynomial**
- $r(x)\in \mathcal{T}(d, d)$, which is a random element.
- **Encrypt**
- $e(x)=p\cdot h(x)\cdot r(x)+m(x)$ mod $q$
- Remark:
- The polynomial $f(x)$ should not contain an equal number of 1s and -1s; otherwise, it will not be invertible in $R_q$ and $R_p$, since $f(x)$ and $x^N - 1$ will share the common factor $x - 1$. Specifically, when $f(x) = \mathcal{T}(d, d)$, we get $f(1) = 0 = 1^N - 1$, implying that $x - 1$ divides both.
- The plaintext $m(x)$ is a polynomial in $R$ that is the center-lift of a polynomial in $R_p$
- If $f(x)$ has no inverse, pick a new one.

## Decryption
- **Decrypt**
- $a(x)=f(x)\cdot e(x)$ mod $q$
- $b(x) = F_p(x) \cdot a(x)=f(x)^{-1} \cdot a(x)$ mod $p$
- $b(x)$ is equal to $m(x)$
- **Proof of correctness**
- If $(N, p, q, d)$ are chosen to satisfy $q > (6d+1)\cdot p$, then $b(x)$ is equal to $m(x)$
\begin{aligned}
a(x) &= f (x) \cdot e(x) \text{ mod } q \\
&= f (x) \cdot (p\cdot h(x) \cdot r(x) + m(x))\text{ mod } q \\
&= p\cdot f (x) \cdot F_q(x) \cdot g(x) \cdot r(x) + f (x) \cdot m(x) \text{ mod } q \\
&= p\cdot g(x) \cdot r(x) + f (x) \cdot m(x) \text{ mod } q
\end{aligned}
- We are not sure if $[e(x) \pmod q]= e(x) \pmod p$
- We need to bound all the coefficients of $𝑎(𝑥)$ to ensure they remain below $𝑞$, preventing any reduction modulo $𝑞$. This guarantees that the original message $𝑚(𝑥)$ can be correctly recovered. i.e. We calculate in $R$ instead of $R_q$
- Let's see how it works.
- $g(x), r(x) \in \mathcal{T}(d, d)$, the largest coefficient of $p\cdot g(x)\cdot r(x)$ is $2d\cdot p$. (smallest one is $-2d\cdot p$)
- $f(x) \in \mathcal{T}(d+1, d)$, and $-\frac{1}{2}p\lt m_i\le\frac{1}{2}p$, the largest coefficient of $f(x)\cdot m(x)$ is $(2d+1)\cdot \frac{1}{2}p$. (smallest one is $-(2d+1)\cdot \frac{1}{2}p$)
- the largest coefficient of $a(x)$ is $2d\cdot p+(2d+1)\cdot \frac{1}{2}p=(6d+1)\cdot \frac{1}{2}p$
- This ensures that the coeffcients of $a(x)$ are in $(-\frac{1}{2}q, \frac{1}{2}q\ ]$, and is equivalent to calculating $a(x)$ in both $R$ and center-lifted $R_q$. Being done in $R$ means modulo $p$ is also correct.
- Finally, We calculate $b(x)$ to retrieve the exact plaintext $m(x)$
\begin{aligned}
b(x) &= F_p(x) \cdot a(x) \text{ mod } p \\
&= f(x)^{-1} \cdot (p\cdot g(x) \cdot r(x) + f (x) \cdot m(x)) \text{ mod } p \\
&= f(x)^{-1} \cdot f (x) \cdot m(x) \text{ mod } p \\
&= m(x) \text{ mod } p \\
\end{aligned}
- **Remark**
- The solution to the NTRU key recovery problem is not unique
- If $(f (x), g(x))$ is one solution, then the rotation $(x^k \cdot f(x), \, x^k \cdot g(x))$ is also a solution for every $0 ≤ k < N$
- More generally, any pair of polynomials $(f (x), g(x))$ with sufficiently small coefficients and satisfying $f (x)\cdot g(x) = h(x)$ serves as an NTRU decryption key

## Scheme Flow

## Brute-force search attack
- Determine whether a private key $f(x)$ is valid by verifying that $f(x)\cdot h(x)$ mod $q$ is a ternary polynomial.
- By first choosing $d_1$ coefficients to be 1 and then choosing $d_2$ of the remaining $N − d_1$ coefficients to be −1, we know
- $\#\mathcal{T}(d1, d2)= \displaystyle \binom{N}{d_1} \displaystyle \binom{N-d_1}{d_2}=\displaystyle \frac{N!}{d_1!d_2!(N − d_1 − d_2)!}$
- The number is maximized when $d_1$ and $d_2$ are both approximately $N/3$

## Collision Attack (Meet-In-the-Middle Attack)
- To be done

## Something need to know
- $f(x)\in \mathcal{T}(d+1, d)$ has small coefficients, but the coefficients of its inverse tend to be randomly and uniformly distributed, so do the public key and ciphertext.
- For example:
- let $N = 11, q = 73$
- $f(x)=x^{10} +x^8 −x^3 +x^2 −1\in \mathcal{T}(3,2)$
- Its inverse has random-looking coefficients
- $F_q(x) = 22x^{10} + 33x^9 + 15x^8 + 33x^7 − 10x^6 + 36x^5 −33x^4 −30x^3 +12x^2 −32x +28$

## Reference
- [NTRU学习笔记](https://0xffff.one/d/1424)
- [High-order masking of NTRU](https://eprint.iacr.org/2022/1188.pdf)
- [NTRU: A Ring-Based Public Key Cryptosystem ](https://www.ntru.org/f/hps98.pdf)
- [NTRU: a high speed public key cryptosystem](https://ntru.org/f/hps96.pdf)
- [Reduced Memory Meet-in-the-Middle Attack
against the NTRU Private Key](https://eprint.iacr.org/2016/177.pdf)