Problem R-LWE rozpatrywany jest zwykle dla krat ideałowych, skonstruowanych w oparciu o wielomiany cyklotomiczne. W tego typu kratach można efektywnie wykonywać obliczenia, używając transformaty NTT. Jednak pewne ataki, wyszukujące ideały główne w pierścieniach cyklotomicznych, są niepokojące dla ogólnego bezpieczeństwa krat cyklotomicznych. Tutaj zauważamy, że pierścienie izomorficzne z kratami cyklotomicznymi to szczególne rodzaje pierścieni grupowych. Do konstrukcji można jednak użyć innych pierścieni grupowych, otrzymując struktury, w których da się liczyć równie efektywnie i zachować wyższe bezpieczeństwo. Post oparty na artykule Chenga, Zhanga i Zhuanga, w którym autorzy badają pierścień grpowy nad grupą dihedralną i liczbami całkowitymi.

Czemu pierścienie grupowe?

Pierścienie cyklotomiczne $\mathbb{Z}/(x^n+1)$ (których ideały są izomorficzne z kratami cyklotomiczymi) są izomorficzne ze składnikiem sumy prostej opisującej pierścień grupowy:

\[\mathbb{Z}[C_{2n}] \approx \mathbb{Z}/(x^{2n}-1) \approx \mathbb{Z}/(x^n+1) \oplus \mathbb{Z}/(x^n-1),\]

gdzie $C_{2n}$ oznacza $2n$-elementową grupę cykliczną. Jest to szczególny przypadek pierścienia grupowego, który ma istotne wady. Przede wszystkim problem stanowi istnienie homomorfizmu w przestrzeń jednowymiarową:

\[\mathbb{Z}[x]/(x^{2n}-1) \rightarrow \mathbb{Z}[x]/(x-1).\]

Tego typu jednowymiarowa reprezentacja nad ciałami skończonymi:

\[\mathbb{Z}_q[x]/f(x) \rightarrow \mathbb{Z}_q[x]/(x-1)\]

może być wykorzystana w atakach zawsze gdy wielomian $(x-1)$ dzieli $f(x)$ nad $\mathbb{Z}_q$.

Inny argument wiąże się z cechą bycia dziedziną ideałów głównych (PID). Wprawdzie $\mathbb{Z}[x]$ nie jest PID, ale już jego dla $\mathbb{Z}_q[x]$ jest, dla dowolnej liczby pierwszej $q$. Jednak pierścień grupowy $\mathbb{Z}_p[G]$ nie musi być PID jeżeli grupa $G$ nie jest przemienna. Ta własność stanowi dodatkową ochronę przeciwko atakom strukturalnym.

Uwaga: nieodwracalne ideały

Istotną różnicą pomiędzy pierścieniami grupowymi i pierściami ilorazowymi użytymi do konstrukcji krat ideałowych jest to, że mają one ideały, które nie są odwracalne. Tutaj trzeba uważać. Bezpieczeństwo R-LWE dla pierścieni grupowych powinno być zdefiniowane przy użyciu ideałów odwracalnych

Normy elementów pierścieni grupowych

Cheng, Zhang i Zhuang wprowadzają nową normę, nie wynikającą z typowych zanurzeń (patrz: pierścienie grupowe a geometria). Rozważmy element $h = \sum_{i=1}^n a_i \cdot g_i \in R[G] \approx R^n$ oraz rozważmy macierz $A(h)$ (transformację liniową z $R^n$ w $R^n$) związaną z mnożeniem przez ten element (można do tego użyć regularnej reprezentacji grup skońcoznych). Teraz normę elementu $h$ definiujemy jako normę odpowiadającej mu macierzy $A(h)$:

\[\|h\|_{Mat} = \sqrt{Norm(A(h) \cdot A(h)^T)} = \sqrt{ ~największa~wartość~własna~macierzy~A(h) \cdot A(h)^T}.\]

Uwaga: dla macierzy diagonalnych jest to to samo co norma maximum $l_{\infty}$, która jest używana gdy stosuje się zanurzenie kanoniczne.

Ideały, ideały dualne i odwracalność

Niech $I$ będzie prawym ideałem w $\mathbb{Z}[G]$, wtedy jego lewy ideał dualny definiujemy jako:

\[I^{-1} = \{ x \in \mathbb{Q}[G] ~|~ \forall y \in I ~ xy \in \mathbb{Z}[G] \}\]

(to działa tak jak definicja kraty dualnej, tyle że tu istotna jest kolejność: ideał jest prawy, a ideał dualny lewy). Lewy ideał dualny jest $\mathbb{Z}[G]$-modułem i można sprawdzić, że zachodzi:

\[I \subseteq \mathbb{Z}[G] \subseteq I^{-1}.\]

Ideał nazwiemy odwracalnym jeżeli $I^{-1} \cdot I = \mathbb{Z}[G]$. Jeżeli ideał $I$ jest odwracalny to $I^{-1}$ jest jego lewym ideałem ułamków, czyli istnieje licza całkowita $t$, taka że $tI^{-1} \subseteq \mathbb{Z}[G]$.

Grupa dihedralna i jej reprezentacje

Grupa dihedralna to jedna z grup nieprzemiennych o najmniejszej nieprzemienności. Jej szczególne własności pozwalają zachować efektywność wykonywania działania na jej elementach. Grupa o $2n$ elementach zdefiniowana jest następująco:

\[D_{2n} = \{ t^i \cdot s^j ~|~ 0 \leqslant i \leqslant n−1,~ 0 \leqslant j \leqslant 1 \},\]

a jej elementy spełniają relacje: $t^n = s^2 = 1$ oraz $sts = t^{−1}$.

Reprezentacje grup przemiennych są jednowymiarowe. Grupa dihedralna ma reprezentacje wymiaru 2 (ale większych nie ma, stąd jest bliska grupom przemiennym). Dla nieparzystych $n$ grupa $D_{2n}$ ma $(n+1)/2$ nierozkładalne reprezentacje, z czego dwie są wymiaru 1, a pozostałe wymiaru 2. Reprezentacje jednowymiarowe:

• $p_0(t^i)=1$ i $p_0(st^i)=1$ (trywialna),
• $p_1(t^i)=1$ i $p_1(st^i)=-1$.

Reprezentacje dwuwymiarowe dla $2 \leqslant k \leqslant (n + 1)/2$ są postaci:

\[p_k(t^i) = \begin{bmatrix} e^{\frac{2 \pi i (k-1)}{n}} & 0 \\ 0 & e^{\frac{-2 \pi i (k-1)}{n}} \end{bmatrix}\] \[p_k(st^i) = \begin{bmatrix} 0 & e^{\frac{2 \pi i (k-1)}{n}} \\ e^{\frac{-2 \pi i (k-1)}{n}} & 0 \end{bmatrix}\]

Twierdzenie Wedderburna

Zgodnie z Twierdzeniem Wedderburna i Maschke’a powyższych reprezentacji można użyć do rozłożenia pierścienia grupowego na następującą sumę prostą:

\[\mathbb{C}[D_{2n}] \approx \mathbb{C} \oplus \mathbb{C} \oplus \bigoplus_{i=2}^{(n+1)/2} \mathbb{C}^{2 \times 2}.\]

Jednowymiarowe reprezentacje są problematczne i mogą prowadzić do ataków. Jeżeli $n$ jest liczbą pierwszą to $(t^{n-1}+t^{n-1}+\cdots + 1) \mathbb{Z}[D_{2n}]$ jest dwustronnym ideałem i pierścień

\[\mathbb{Z}[D_{2n}]/(t^{n-1}+t^{n-1}+\cdots + 1) \mathbb{Z}[D_{2n}]\]

jest dobrze zdefiniowany i może być zrzutowany na $\bigoplus_{i=2}^{(n+1)/2} \mathbb{C}^{2 \times 2}$. Innym pierścieniem bez jednowymiarowych reprezentacji jest pierścień zdefiniowany dla $n$ będącego potęgą dwójki:

\[R = \mathbb{Z}[D_{2n}]/(t^{n/2} + 1) \mathbb{Z}[D_{2n}].\]

Tego pierścienia używają Chen, Zhang i Zhuang w swojej wersji R-LWE na pierścieniach grupowych.

Odwracalność elementów $R$

Następujący lemat opisuje kiedy elementy $R$ są odwracalne.

Lemat Element:

\[\sum_{0 \leqslant i \leqslant n/2-1} a_i t^i + \sum_{0 \leqslant i \leqslant n/2-1} b_i s t^i \in R\]

jest odwracalny w $R \otimes \mathbb{Q}$ wtedy i tylko wtedy gdy dla wszystkich nieparzystych $1 \leqslant k \leqslant n/2$:

\[\| \sum_{0 \leqslant i \leqslant n/2-1} a_i e^{-2 \pi \sqrt{-1} ki/n}\| - \| \sum_{0 \leqslant i \leqslant n/2-1} b_i e^{-2 \pi \sqrt{-1} ki/n}\| \neq 0,\]

gdzie norma jest normą zespoloną.

R-LWE w pierścieniach grupowych

Niech:

\[R_{\mathbb{R}} = R \otimes_{\mathbb{Z}} \mathbb{R} \approx \mathbb{R}[D_{2n}]/(t^{n/2} + 1) \mathbb{R}[D_{2n}],\]

będzie pierścieniem izomorficznym z $\mathbb{R}^n$ po wykonaniu zanurzenia współczynnikowego. Niech:

\[\mathbb{T} = R_{\mathbb{R}}/R.\]

Ponadto niech:

\[R_q = \mathbb{Z}_q[D_{2n}]/(t^{n/2} + 1) \mathbb{Z}_q[D_{2n}].\]

Używając zdefiniowanych powyżej struktur możemy wprowadzić rozkład Gaussa i zdefiniować problem R-LWE.

Definicja R-LWE

Niech $\chi_{\alpha_1,\alpha_2,\ldots,\alpha_n}$ będzie rozkładem Gaussa na $\mathbb{R}^n$, takim że:

\[\chi_{\alpha_1,\alpha_2,\ldots,\alpha_n}(x_1,x_2,\ldots,x_n) = e^{-\pi ((x_1/\alpha_1)^2 + (x_2/\alpha_2)^2 + \cdots (x_n/\alpha_n)^2)}.\]

Niech rozkład $\psi_{\leqslant \alpha}$ będzie zbiorem rozkładów takich, że $\alpha_i \leqslant \alpha$ dla $1 \leqslant i \leqslant n$. Problem $R_q$-LWE polega na znalezieniu $s \in R_q$ znając ciąg par $(a_i,b_i) \in R_q \times \mathbb{T}$, gdzie $a_i$ są wybierane niezależnie i jednostajnie od rozkładu $R_q$, $b_i = a_i \cdot s / q + e_i \mod{R}$, a $e_i$ jest wybierany niezależnie z rozkładu $\chi \in \psi_{\leqslant \alpha}$.

Normy elementów $\mathbb{R}[D_{2n}]$

Żeby pokazać trudność problemu R-LWE w pierścieniu grupowym $\mathbb{R}[D_{2n}]$ musimy zbadać macierzowe normy jego elementów i oszacować od góry ich rozmiar.

Lemat Dowolny element pierścienia $\mathbb{R}[D_{2n}]$ ma postać:

\[h = f(t) + s \cdot g(t)\]

dla pewnych wielomianów $f(x)$ i $g(x)$ o współczynnikach rzeczywistych. Wtedy wartości własne macierzy $A(h) \cdot A(h)^T$ są postaci $(|f(\omega^i)| \pm |g(\omega^i)|)^2$ dla $\omega=e^{2 \pi i/n}$ (n-ty pierwiastek z jedynki), a norma jest normą w $\mathbb{C}$. Stąd norma $h$ jest ograniczona z góry przez wartość $max${$|f(\omega^i)| + |g(\omega^i)| ~|~i=0,1,\ldots n-1$}.

Lemat Dla każdego odwracalnego prawego ideału $I \subseteq \mathbb{Z}[D_{2n}]$, niech $I^{-1}$ będzie lewą odwrotnością. Niech $L$ i $L^{-1}$ będą kratami zdefiniowanymi przez zanurzenie współczynników $I$ i $I^{-1}$. Wtedy kraty $L^{\star}$ i $L^{-1}$ są takie same z dokładnością do permutacji współrzędnych.

Efektywność obliczeń

Twierdzenie Mnożenie elementów w $\mathbb{Z}{q}$ [$D{2n}$] można wykonać ze złożonością czasową $\tilde{O}(n \log{q})$.

Dowód Niech $f_1 + sf_2$ i $f_3 + sf_4$ będą dwoma elementami $\mathbb{Z}q$ [$D{2n}$], gdzie $f_1$, $f_2$, $f_3$ i $f_4$ są wielomianami zmiennej $t$. Iloczyn elementów będzie postaci:

\[(f_1 + s f_2) \cdot (f_3 + s f_4) = f_1 f_3 + s f_2 f_3 + f_1 s f_4 + s f_2 s f_4 =\] \[= f_1 f_3 + s f_2 f_3 + s (s f_1 s) f_4 + (s f_2 s) f_4 =(f_1 f_3 + (s f_2 s) f_4 ) + s (f_2 f_3 + (s f_1 s) f_4),\]

gdzie $s f_1 s$ i $s f_2 s$ są wielomianami zmiennej $t$, które można obliczyć w czasie liniowym. Żeby obliczyć iloczyn musimy zatem wykonać cztery mnożenia w pierścieniu $\mathbb{Z}_q[t]$ co można zrobić w czasie $\tilde{O}(n \log{q})$.

Bezpieczeństwo

Główny ciężar artykułu leży właśnie tutaj. Zdefiniowaliśmy nową strukturę (dihedralny pierścień grupowy), pokazaliśmy, że można w nim efektywnie wykonywać obliczenia, a nieprzemienność struktury pozwala uniknąć części ataków. Czy jednak problem LWE w tym pierścieniu jest równie trudny jak w pierścieniach cyklotomicznych używanych przez Regeva? Pozytywnej odpowiedzi na powyższe pytanie dowodzi następujące twierdzenie. Niestety twierdzenie korzysta z wielu parametrów, co czyni jego sformułowanie nieintuicyjnym i męczącym dla czytelnika.

Twierdzenie Niech $\alpha = \alpha(n) \in (0,1)$ i niech $q = q(n)$ będzie liczbą pierwszą spełniającą:

\[\alpha q \geqslant \sqrt{n \omega} (\sqrt{\log{n}}).\]

Mając daną wyrocznię rozwiązującą problem R-LWE dla dihedralnego pierścienia grupowego z parametrami $q$ i $\psi_{\leqslant \alpha}$ w wersji average case (czyli pewną losową instancję problemu, w kontraście do worst case, czyli najtrudniejszego przypadku), istnieje kwantowy algorytm działający w czasie wielomianowym, który rozwiązuje problem SVP dla dowolnego odwracalnego ideału $I$ w pierścieniu $R$ w czasie $\tilde{O}(n/\alpha)$.

Idea dowodu Dowód naśladuje dowód Regeva dla pierścieni cyklotomicznych. Dysponując wyrocznią rozwiązującą problem R-LWE w digedralnym pierścieniu grupowym, można wygenerować próbki z dyskretnego rozkładu Gaussa na $I$ o szerokości $\lambda_n \sqrt{n \omega} \log{n}/\alpha$, rozpoczynając od dostatecznie dużej szerokości $r \geqslant 2^{2n} \lambda_n(I)$, gdzie dowolna wielomianowa liczba próbek może być wygenerowana klasycznie. Próbki z tego rozkładu mają normy euklidesowe długości ograniczonej z góry przez wartość $\sqrt{n} \lambda_n(I) \sqrt{n \omega} \log{n}/\alpha$ prawie na pewnio. Próbki rozwiązują zatem problem SVP dla ideału $I$ z dokładnością do czynnika $\tilde{O}(n/\alpha)$.

Dowód Regeva

Jako że dowód naśladuje dowód Regeva dla pierścieni cyklotomicznych, prześledźmy głowne pomysły Regeva.

1. Rozwiązanie problemu dyskretnego próbkowania rozkładu Gaussa na kracie $L$ (DGS - discrete gaussian sampling) dla rozkładu o niewielkiej szerokości $r$.

2. Redukcja problemu DGS na kracie $L$ do problemu $\beta-BDD$ (znajdywania najbliższego wektora kraty, jeżeli wiemy, że leży on w odległości zależnej od $\beta$) na kracie dualnej $L^{\star}$. Ta redukcja zakład użycie algorytmu kwantowego (nie jest możliwa na komputerze klasycznym).

3. Sprowadzenie problemu $\beta-BDD$ do $(q,\beta)-BDD$. Parametr $q$ określa nową modularnać: rozważamy wektory modulo $qL^{\star}$.

4. Sprowadzenie problemu $(q,\beta)-BDD$ na $L$ do problemu DGS na $L^{\star}$ dla rozkładu o większej szerokości. Ten krok wymaga wyroczni R-LWE.

5. I tak w kółko. Aż dostaniemy DGS o szerokości, która pozwala rozwiązać SVP w czasie wielomianowym.

Jak używana jest wyrocznia R-LWE

Szczególnie warto omówić krok, w którym wykorzystywana jest wyrocznia R-LWE. Rozważmy zatem problem $(q,\beta)-BDD$ na kracie $L^{\star}$. Mamy pewien wektor $y=x+e$, gdzie $x$ należy do kraty $x \in L^{\star}$, a $e$ jest błędem o ograniczonej długości $|e| \leqslant \beta \lambda_1(L^{\star})$. Chcemy znaleźć $x \pmod{qL^{\star}}$.

Korzystając z DGS umiemy wylosować wektor $z \in L$ długości $|z| \leqslant m/\lambda_1(L^{\star})$, gdzie $m \geqslant q\sqrt{n}$. Stąd:

\[m/\lambda_1(L^{\star}) \geqslant q\sqrt{n}/\lambda_1(L^{\star}) \approx q \eta(L) \approx \eta(qL),\]

gdzie przez $\eta$ oznaczamy parametr wygładzający wybranej kraty (smoothing parameter).

Rozważmy element $z \mod{qL}$. Odpowiada on losowemu elementowi $a \in \mathbb{Z}_q^n$, co można pokazać używając parametru wygładzającego. Możemy obliczyć $a$ zapisując współczynniki $z$ modulo $q$ w bazie $B$ (wtedy $z=aB$). Nie możemy po prostu zapisać współczyników $z$, bo nie wiemy czy krata $L$ nie musi być q-kratą, ani nawet kratą całkowitoliczbową (integral lattice). Może być dowolna. Jakich zatem własności oczekujemy od $B$?

Istnieje przekształcenie zadane przez macierz $B$ z $\mathbb{Z}_q^n$ w $L$ spełniające $\psi B = 1$, gdzie $\psi$ zadaje ciąg dokładny $\mathbb{Z}$-modułów:

\[0 \rightarrow qL \rightarrow L \stackrel{\psi}{\rightarrow} \mathbb{Z}_q^n \rightarrow 0.\]

Samo $B$ nie jest homomorfizmem $\mathbb{Z}$-modułów. Niech teraz:

\[b = z(x + e)^T = zx^T + ze^T \mod{q \mathbb{Z}},\]

oraz niech $s = xB^T$. Zauważmy, że:

\[\| ze^T \|_{\infty} \leqslant m \beta,\] \[zx^T = aBx^T = aB(s(B^{-1})^T)^T = as.\]

Wyrocznia R-LWE może zwrócić $s$, na podstawie którego można obliczyć $x \mod{qL^{\star}}$ - a więc szukany najbliższy wektor - co dopełni redukcję. Warto podkreślić jak istotne jest wykorzystywanie krat dualnych.