1.3. NTRU¶

Đối với NTRU-HRSS mình sử dụng bài thuyết trình ở dự án PQC của NIST [1].

Đối với NTRUEncrypt thì mình tham khảo [33] (chương 7 về lattice). Mình sẽ sử dụng kí hiệu từ tài liệu này làm chuẩn cho cả NTRUEncrypt, NTRU-HRSS và NTRU.

1.3.1. Tham số cho NTRU¶

Các thuật toán NTRU hoạt động dựa trên các vành thương (quotient ring) sau:

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

trong đó $p$, $q$ và $n$ là các số nguyên tố khác nhau.

Ta cần định nghĩa một phép biến đổi gọi là center-lift. Trong các tài liệu khác thì gọi là phép modular reduction.

Với số nguyên $n$ cố định đóng vai trò modulo, ta xét phần tử

\[r \in \{ 0, 1, \ldots, n - 1 \}.\]

Khi đó center-lift của $r$ là số $r' \in \mathbb{Z}$ sao cho $-\dfrac{n}{2} < r' \leqslant \dfrac{n}{2}$ và $r \equiv r' \pmod{n}$.

Ví dụ, khi $n = 8$:

với $r = 3$ thì $r' = 3$;
với $r = 6$ thì $r' = -2$.

Ta cần thêm tập

\[\begin{split}\mathcal{T}(d_1, d_2) = \left\{\begin{array}{cl} & : a(x) \ \text{có đúng} \ d_1 \ \text{hệ số bằng} \ 1 \\ a(x) \in R & : a(x) \ \text{có đúng} \ d_2 \ \text{hệ số bằng} \ -1 \\ & : a(x) \ \text{có các hệ số còn lại là} \ 0. \end{array}\right\}.\end{split}\]

1.3.2. NTRUEncrypt¶

1.3.2.1. Tạo khóa¶

Chọn $f(x) \in \mathcal{T}(d+1, d)$ và $g(x) \in \mathcal{T}(d, d)$ ngẫu nhiên.

Ta tính

\[\begin{split}F_q(x) = f(x)^{-1} \in R_q, \\ F_p(x) = f(x)^{-1} \in R_p.\end{split}\]

Tiếp theo, tính

\[h(x) = F_q(x) \cdot g(x) \in R_q.\]

Khi đó, private key là cặp $(f(x), F_p(x))$ và public key là $h(x)$.

1.3.2.2. Mã hóa¶

Giả sử bản rõ là đa thức $m(x) \in R$ sao cho hệ số $m_i$ thỏa $-\dfrac{p}{2} < m_i \leqslant \dfrac{p}{2}$ (center-lift hệ số).

Chọn ngẫu nhiên đa thức $r(x) \in \mathcal{T}(d, d)$ và tính

\[e(x) = p \cdot h(x) \cdot r(x) + m(x) \pmod{q}.\]

Khi đó bản mã là $e(x) \in R_q$.

1.3.2.3. Giải mã¶

Để giải mã, ta tính

\[a(x) = f(x) \cdot e(x) \pmod{q}.\]

Sau đó ta center-lift các hệ số của $a(x)$ thành đa thức thuộc $R$ rồi tính trong modulo $p$:

\[b(x) = F_p(x) \cdot a(x) \pmod{p}.\]

Khi đó $b(x)$ chính là bản rõ $m(x)$ ban đầu.

Ở đây, điều kiện của các tham số $n$, $p$, $q$ và $d$ để NTRUEncrypt hoạt động đúng là

\[\boxed{q > (6d + 1) p.}\]

1.3.2.4. Tính đúng đắn của quá trình giải mã¶

Ta có

\[\begin{split}a(x) & \equiv f(x) \cdot e(x) \pmod{q} \\ & \equiv f(x) \left(p \cdot h(x) \cdot r(x) + m(x)\right) \pmod{q} \\ & \equiv p \cdot f(x) \cdot h(x) \cdot r(x) + f(x) \cdot m(x) \pmod{q} \\ & \equiv p \cdot f(x) \cdot r(x) \cdot F_q(x) \cdot g(x) + f(x) \cdot m(x) \pmod{q} \\ & \equiv p \cdot g(x) \cdot r(x) + f(x) \cdot m(x) \pmod{p}\end{split}\]

vì $f(x) \cdot F_q(x) \equiv 1 \pmod{q}$.

Xét đa thức $p \cdot g(x) \cdot r(x) + f(x) \cdot m(x)$ trong $R$ (center-lift). Ta có

\[\begin{split}b(x) & \equiv F_p(x) \cdot a(x) \pmod{p} \\ & \equiv \underbrace{F_p(x) \cdot p \cdot g(x) \cdot r(x)}_{0} + \underbrace{F_p(x) \cdot f(x)}_{1} \cdot m(x) \pmod{p} \\ & \equiv m(x) \pmod{p}.\end{split}\]

1.3.2.5. NTRU lattice¶

Đặt public key

\[h(x) = h_0 + h_1(x) + \cdots + h_{n-1} x^{n-1},\]

các hệ số đa thức tương ứng với vector

\[\bm{h} = (h_0, h_1, \ldots, h_{n-1}).\]

Đặt

\[\begin{split}M^{\text{NTRU}}_{\bm{h}} = \left(\begin{array}{cccc|cccc} 1 & 0 & \cdots & 0 & h_0 & h_1 & \cdots & h_{n-1} \\ 0 & 1 & \cdots & 0 & h_{n-1} & h_0 & \cdots & h_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & h_1 & h_2 & \cdots & h_0 \\ \hline 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q \end{array}\right) = \left(\begin{array}{c|c} \bm{I}_n & \bm{h} \\ \hline \bm{O}_n & q \bm{I}_n \end{array}\right),\end{split}\]

ở đây $\bm{I}_n$ là ma trận đơ đơn vị cấp $n$, $\bm{O}_n$ là ma trận không cấp $n$.

Giả sử

\[\begin{split}a(x) & = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}, \\ b(x) & = b_0 + b_1 x + \cdots + b_{n-1} x^{n-1},\end{split}\]

tương ứng với các vector

\[\bm{a} = (a_0, a_1, \ldots, a_{n-1}), \quad \bm{b} = (b_0, b_1, \ldots, b_{n-1}).\]

Ta kí hiệu

\[(\bm{a}, \bm{b}) = (a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}) \in \mathbb{Z}^{2n}.\]

Giả sử $f(x) \cdot h(x) \equiv g(x) \pmod{q}$, đặt $u(x) \in R$ là đa thức thỏa

\[f(x) \cdot g(x) = g(x) + q \cdot u(x).\]

Khi đó

\[(\bm{f}, -\bm{u}) \cdot M^{\text{NTRU}}_{\bm{h}} = (\bm{f}, \bm{g})\]

nên vector $(\bm{f}, \bm{g})$ thuộc lattice $L^{\text{NTRU}}_{\bm{h}}$.

1.3.3. NTRU-HRSS¶

Hệ mật mã NTRU-HRSS được nộp vòng 1 của dự án NIST PQC. Ở vòng 2, NTRU-HRSS hợp nhất với NTRUEncrypt trở thành NTRU.

1.3.3.1. Tạo khóa¶

Đối với NTRU-HRSS cần thêm các vành con của $R_p$ và $R_q$ xác định bằng đa thức cyclotomic. Ta kí hiệu đa thức cyclotomic thứ $d$ là $\Phi_d$. Nhận xét bên trên:

$\Phi_1(x) = x - 1$;
nếu $d$ là số nguyên tố thì

\[\Phi_d(x) = 1 + x + \ldots + x^{d-1}.\]

Đặt $S_p = \dfrac{(\mathbb{Z} / p\mathbb{Z})[x]}{\Phi_n(x)}$ và $S_q = \dfrac{(\mathbb{Z} / q\mathbb{Z})[x]}{\Phi_n(x)}$ với $p$, $q$ và $n$ là các số nguyên tố như trên.

Hơn nữa, Khi $n$ là số nguyên tố thì $x^n - 1 = Phi_1(x) Phi_n(x)$ và do đó

\[R_p \cong \dfrac{(\mathbb{Z} / p\mathbb{Z})[x]}{\Phi_1(x)} \times S_p, \quad R_q \cong \dfrac{(\mathbb{Z} / q\mathbb{Z})[x]}{\Phi_1(x)} \times \mathcal{S}_q.\]

Thông thường ta chọn $p = 3$ và $n = 701$. Việc chọn $n$ như vậy được (nhiều) người khẳng định là an toàn.

Đối với NTRU-HRSS-PKE, private key là một phần tử khác không $f \in S_p$.

Từ $f$ ta tính public key $h = \Phi_1(x) \cdot g \cdot f^{-1} \in R_q$ với một phần tử $g \in S_p$. Điều này đòi hỏi $f$ khả nghịch trong $R_q$.

Để hỗ trợ giải mã ta cần nghịch đảo của $f$ trong $S_p$. Ta viết nghịch đảo của $f$ trong $R_q$ và $S_p$ tương ứng là là $f^{-1}_q$ và $f^{-1}_p$.

Theo cấu trúc thì $f$ khả nghịch trong cả $S_p$ và $\mathcal{S}_q$.

Thay vì lấy $f$ và $g$ trực tiếp từ $S_p$ thì ta lấy từ tập con:

\[\mathcal{T}^+ = \{ v \in S_p : \langle xv, v \rangle \geqslant 0 \}.\]

Thuật toán sinh khóa gồm các bước:

$f \gets \mathcal{T}^+$.
$f^{-1}_p \gets f^{-1} \in S_p$.
$f^{-1}_q \gets f^{-1} \in \mathcal{S}_q$.
$g \gets \mathcal{T}^+$.
$h = \Phi_1(x) \cdot g \cdot f^{-1} \in R_q$.
Trả về public key là $\text{pk} = h$ và private key là $\text{sk} = (f, f^{-1}_p)$.

1.3.3.2. Mã hóa¶

Gọi $m \in S_p$ là encode của bản rõ và $r \in S_p$ được chọn ngẫu nhiên.

Bản rõ $e$ được tính:

\[e \gets p \cdot r \cdot h + [m]_3 \in R_q\]

Ở đây $p = 3$ là số nguyên tố bên trên.

1.3.3.3. Giải mã¶

Input: $(e, (f, f^{-1}_3))$ và hai vành $(R_q, S_p)$.

Output: plaintext $m'$:

\[m' \gets [e \cdot f]_q \cdot f^{-1}_3 \in S_p.\]

Ở đây kí hiệu $[e \cdot f]_q$ nghĩa là phép tính diễn ra trong vành $R_q$. Tương tự ở trên $[m]_3$ là encode của thông điệp $m$ trong $S_p$.