GGH15
Kryptosystem GGH15 jest jednym z trzech rozwiązań kandydujących na schemat kryptograficznego zaciemniania programów. Jego bezpieczeństwo ma opierać się na trudności problemu kratowego LWE.
Problem LWE
Niech $ \mathbb{T} = \mathbb{R}/\mathbb{Z}$ oznacza odcinek [0,1), $\phi$ będzie rozkładem prawdopodobieństwa na $ \mathbb{T}$. Niech $s \in \mathbb{Z}_q^n$ będzie ustalonym wektorem. Niech
- $a$ pochodzi z rozkadu jednostajengeo na $\mathbb{Z}_q^n$,
- $e \in \mathbb{T}$ pochodzi z rozkładu $\phi$,
- $t = a \cdot s /q + e$, gdzie dzielenie przez $q$ jest homomorfizmem $\mathbb{Z} \rightarrow \mathbb{T}$.
Problem LWE polega na znalezieniu $s$ mając dostęp do dowolnie wielu losowych par $(a,t) \in \mathbb{Z}_q^n \times \mathbb{T}$.
Jak szyfrować macierze przy użyciu LWE?
Załóżmy, że zamiast jednego wektora $s \in \mathbb{Z}_q^n$, mamy $n$ takich wektorów $s_j$ tworzących kolumny macierzy $S \in \mathbb{Z}_q^{n \times n}$. Wybierzmy losowo z rozkładem jednostajnym $n$ wektorów $a_i$ tworzących wiersze macierz $A \in \mathbb{Z}_q^{n \times n}$, a następnie $n^2$ elementów $e$ z rozkładu $\phi$ tworzących macierz $E \in \mathbb{T}^{n \times n}.$ Możemy obliczyć macierz
\[T = A \cdot S + E.\]Poszczególne elementy $t_{ij}$ macierzy $T$ są postaci $t_{ij} = a_i \cdot s_j + e_{ij}$. Trudność odkrycia wektorów $s_j$ przy znajomości macierzy $t_{ij}$ i $a_i$ wynika z trudności problemu LWE. Podobnie znając macierze $T$ i $A$ trudno jest znaleźć macierz $S$. Generalnie skleiliśmy wiele instancji problemu LWE w macierz.
Schemat GGH15
Pełna nazwa schematu GGH15 brzmi Graph-Induced Multilinear Maps from Lattices. Konstrukcja proponuje zgradowany schemat szyfrowania homorficznego. Wykonywane obliczenia reprezentowane są jako graf skierowany. Wierzchołkom grafu przyporządkowywane są jawne macierze. Prywatne elementy można szyfrować w odniesieniu do ścieżek w grafie, wykorzystując macierze z wierzchołków.
Dla przykładu rozważmy ścieżkę $u \rightarrow v$, nad którą chcemy zaszyfrować tajną macierz $S$. Niech wierzchołkom $u$ i $v$ odpowiadają maciezrze $A_u$ i $A_v$. Używając problemu LWE możemy zaszyfrować $S$ obliczając
\[V = A_v S + E_v.\]Załóżmy, że posiadamy pewien tajny parametr $\tau_u$ który pozwala wygenerować macierz $D$ taką, że $D \cdot A_u = V$. Wektor $D$ będzie stanowił szyfrogram maciezry $S$ w odneisieniu do ścieżki $u \rightarrow v$. Zakładając, że problem LWE jest trudny, nie da się odkryć macierzy $S$ znając macierze $V$ i $A_v$. Znajomość macierzy $D$ i $A_u$ pozwala obliczyć $V$, ale nic więcej.
Zauważmy, że mając dwa szyfrogramy nad tą samą ścieżką dysponujemy dwoma równaniami:
\[D_1 A_u = A_v S_1 + E_1, \\ D_2 A_u = A_v S_2 + E_2.\]Równania te możemy dodać otrzymując
\[(D_1+D_2) A_u = A_v (S_1+S_2) + (E_1+E_2).\]czyli szyfrogram sumy $S_1+S_2$ nad tą samą ścieżką. Z łatwością możemy też obliczyć szyfrogram macierzy przeciwnej do $S_1$
\[(- D_1) A_u = A_v (-S_1) + (-E_1).\]Nie możemy jednak w ten sposób obliczyć iloczynu szyfrogramów odpowiadających tej samej ścieżce. Możemy to wykonać dla szyfrogramów, które odnoszą się do ścieżek, które mają wspólny wierzchołek, będący końcem jednej, a początkiem drugiej. Rozważmy dwie ścieżki $u \rightarrow v$ i $v \rightarrow w$. oraz szyfrogramy względem nich
\[D_1 A_u = A_v S_1 + E_1, \\ D_2 A_v = A_w S_2 + E_2.\]Mnożąc pierwsze równanie stronami przez $D_2$ i podstawiając drugie równanie otrzymamy:
\[D_2 D_1 A_u = (D_2 A_v) S_1 + D_2 E_1 = (A_w S_2 + E_2) S_1 + D_2 E_1 = A_w (S_2 S_1) + (E_2 S_1 + D_2 E_1)\]a więc poprawny szyfrogram macierzy $S_2 S_1$ w odniesieniu do złączonej ścieżki $u \rightarrow w$.
Aby schemat spełniał własności szyfru z gradacją, musimy jeszcze mieć możliwość odszyfrowania macierzy identycznościowej (elementu zerowego). Taka procedura nazywana jest Zero-testem.