Opis szyfrowania NTRU i jak jego bezpieczeństwo opiera sie na problemach kratowych.

Schemat NTRU

Niech $R = \mathbb{Z}[x]/(x^N-1)$ będzie pierścieniem obciętych wielomianów z mnożeniem $\star$ jako splotem (opis niżej). Schemat opisuje trójka parametrów $(N, p, q)$ taka, że $N$ jest liczbą pierwszą, $q>p$ oraz $p \perp q$,

Niech $F, G \in R$ wielomiany o współczynnikach ze zbioru $\{-1,0,1\}$ spełniające

\[f = 1 + pF, \\ g = pG.\]

Klucz prywatny: $F,G,f,g$
Klucz publiczny: $h=f^{-1} \star g \pmod{q}$

Aby zaszyfrować wiadomości reprezentujemy ją jako wielomian $m$ o współczynnikach ze zbioru $\{-1,0,1\}$, wybieramy losowy wielomian $r$ o współczynnikach ze zbioru $\{-1,0,1\}$ i obliczamy szyfrogram

\[e = r \star h + m \pmod{q}\]

Deszyfrowanie polega na obliczeniu ioczynu szyfrogram i tajnego wielomianu $f$ modulo $q$:

\[a = f \star e \pmod{q} \equiv f \star (r \star h + m) \equiv f \star (r \star f^{-1} \star g + m) \equiv r \star g + f \star m,\]

i wykonaniu redukcji modulo $p$

\[a \pmod{p} \equiv r \star g + f \star m \equiv r \star pG + (1+pF) \star m \equiv m,\]

Z powyżwszego opisu nie widać od razu, że NTRU jest kryptosystemem kratowym. Nie powiedzieliśmy też, dlaczego trudno jest odzyskać wiadomość i tajne parametry na podstawie publicznych informacji:

• dlaczego trudno jest znaleźć $m$ na podstawie $e = r \star h + m$,
• dlaczego trudno jest znaleźć $f$ i $g$ na podstawie $h$.

Najpierw, krótko opiszę czym właściwie jest splot i modularne macierze splotów.

Sploty i modularne kraty splotu

Weźmy dwa wektory

\[h = [h_0, h_1, \ldots, h_{N-1}] \in \mathbb{Z}^N, \\ f = [f_0, f_1, \ldots, f_{N-1}] \in \mathbb{Z}^N.\]

Ich splotem nazwiemy wektor $g = h \star f$, którego współczynniki są zadane jako

\[g_k = \sum_{i+j \equiv k \pmod{N}} h_if_j.\]

Dodanie operacji splotu wektorów do kraty $\mathbb{Z}^N$ przekształca ją w pierścień izomorficzny z pierścieniem obciętych wielomianów $\mathbb{Z}[x]/(x^N-1)$.

Niech $q \geqslant 1$ będzie liczbą całkowitą nazywaną modułem. Niech $h \in \mathbb{Z}^N$. Zbiór par $(f,g) \in \mathbb{Z}^{2N}$ spełnaijacych $h \star f = g \pmod{q}$ tworzy kratę w $\mathbb{Z}^{2N}$. Kratę tę oznaczamy $L_h = L(h,q)$ i nazywamy modularną kratą splotu (convolution modular lattice).

\[L_h = \{ (f,g) \in \mathbb{Z}^{2N}~|~ h \star f \equiv g \pmod{q} \}.\]

Krata $L_h$ jest rozpięta przez wektory będące wierszami macierzy reprezentującej formułę splotu

\[L_h = RowSpan \begin{bmatrix} Id & circ(h) \\ 0 & q \cdot Id \end{bmatrix},\]

gdzie macierz $circ(h)$ jest macierzą cykliczną generowaną przez wektor $h$ i ma postać

\[circ(h) = \begin{bmatrix} h_0 & h_1 & \ldots & h_{N-1} \\ h_{N-1} & h_0 & \ldots & h_{N-2} \\ \vdots & \vdots & \vdots & \vdots \\ h_1 & h_2 & \ldots & h_0 \\ \end{bmatrix}\]

Sprawdżmy, że wektor $(f,g)$ rzeczywiście należy do kraty. Z założenia dla pewnego $u \in \mathbb{Z}^N$:

\[h \star f - g = u \cdot q,\]

a stąd

\[[f,g] = [f,u] \cdot \begin{bmatrix} Id & circ(h) \\ 0 & q \cdot Id \end{bmatrix} \in L_h.\]

Bezpieczeństwo NTRU

Zauważmy teraz, że zgodnie z oznaczeniami z początku klucze schematu NTRU wybierane są tak, żeby

\[h \star f \equiv g \pmod{q}\]

oraz tak, aby $f$ i $g$ miały małe parametry. Wynika stąd, że krata $L_h$ musi zawierać krótki wektor $(f,g)$. Ze względu na trudność problemu SVP szukania najkrótszego wektora kraty ciężko jest znaleźć taki wektor.

Rozważmy teraz szyfrowanie wiadomości

\[e = r \star h + m \pmod{q}.\]

Można je zapisać w postaci wektorowej w następujący sposób

\[[0,e] = [0,r \star h + m \pmod{q}] = [r,r \star h \pmod{q}] + [-r,m].\]

Wektor $[r, r \star h]$ należy do kraty $L_h$. Wektor $[-r,m]$ ma tylko małe współczynniki, jest krótki i nie należy do kraty $L_h$. Stąd wektor $[0,e]$ również nie należy do kraty. Znalezienie wektora $[-r,m]$ (i tym samym wiadomości $m$) na podstawie $[0,e]$ wymagałoby znalezienia wektora kraty $[r, r\star h \pmod{q}] \in L_h$ leżącego najbliżej $[0,e]$ i tym samym rozwiązania problemu CVP znajdywania wektora kraty leżącego najbliżej ustalonego wektora z poza kraty.