Wieloliniowość wyznaczników i ich rola w szyfrowaniu obliczeń.

Możemy rozpatrywać wyznaczniki macierzy nad ciałami i macierzy nad pierścieniami. Tu będziemy się zajmować wyznacznikami nad pierścieniami przemiennymi (być może ciałami). Dla pierścieni nieprzemiennych definicja wyznacznika musi zostać zmieniona. Różne próby są podejmowane.

Definicja wyznacznika

Wyznacznik macierzy $A=(a_{i,j})){1,1}^{n,n}$ definiujemy jako:

\[det(A) = \sum_{\sigma \in S_n} sgn(\sigma) \cdot a_{1,\sigma(1)} \cdot a_{2,\sigma(2)} \cdots a_{n,\sigma(n)}),\]

gdzie $sgn(\sigma)=\pm 1$ oznacza znak permutacji $\sigma$, który jest równy jeżeli permutację da się przedstawić w postaci złożenia parzystej liczby transpozycji, a -1 w przeciwnym wypadku.

Własności wyznacznika

Wyznacznik macierzy nad pierścieniem R jest przekształceniem R-wieloliniowym alternującym. Oznacza to, że spełnia następujące własności. Niech $A_1, A_2, \ldots, A_n$ będą kolumnami pewnej macierzy $A$ wymiaru $n \times n $ zdefiniowanej nad pierścieniem R:

1. $det[A_1,\ldots,\lambda A_i,\ldots,A_n] = \lambda \cdot det[A_1,\ldots,\lambda A_i,\ldots,A_n]$,

2. $det[A_1,\ldots,A_i + A_i’,\ldots,A_n] = det[A_1,\ldots,A_i,\ldots,A_n] + det[A_1,\ldots,A_i,\ldots,A_n]$,

3. $det[A_1,\ldots,A_i, \ldots, A_j,\ldots,A_n] = - det[A_1,\ldots,A_j, \ldots, A_i,\ldots,A_n]$.

Ponadto dla macierzy nad pierścieniami przemiennymi prawdą jest, że:

\[det(A \cdot B) = det(A) \cdot det(B).\]

Lemat Macierz A nad R jest odwracalna wtedy i tylko wtedy kiedy jej wyznacznik jest elementem odwracalnym w R.

Więcej na ten temat moż na przeczytać w książce [1].

Wyznacznik a obliczenie

Wylosujmy pewną macierz zadaną przez kolumny: $A = [A_1,A_2,\ldots,A_n]$. Rozważmy jej dwie modyfikacje:

\(A_{\lambda} = [\lambda_1 A_1, \lambda_2 A_2, \ldots, \lambda_n A_n],\) \(A_{\alpha} = [\alpha_1 A_1, \alpha_2 A_2, \ldots, \alpha_n A_n].\)

Wtedy:

\[det(A_{\lambda}) = \prod_i \lambda_i \cdot det(A),\] \[det(A_{\alpha}) = \prod_i \alpha_i \cdot det(A).\]

A korzystając z R-wieloliniowości, wyznacznik sumy macierzy ma postać:

\[det(A_{\lambda} + A_{\alpha}) = \sum_i \lambda_i \cdot \sum_i \alpha_i \cdot det(A).\]

Dodając macierze wykonujemy pewne działanie złożone z dodawania i mnożenia na skalarach, przez które wymnożyliśmy kolumny bazowej macierzy $A. Obliczenia te będą mogły być zaszyfrowane (następna sekcja).

Przykład Rozważmy macierz pełnego rzędu $2 \times 2$ zadaną kolumnami $A=[A_1,A_2]$ i spróbujmy zrealizować następujące obliczenia: $x + y$ oraz $x \cdot y.$

W pierwszym przypadku tworzymy macierze $A_x = [x A_1, k A_2]$ oraz $A_y = [y A_1, (1-k) A_2]$. Zauważmy, że:

\[det(A_x+A_y) = det([(x+y) A_1, A_2]) = (x+y) \cdot det(A).\]

W drugim przypadku tworzymy macierze $A_x = [(x-1) A_1, A_2]$ oraz $A_y = [A_1, (y-1) A_2]$. Zauważmy, że:

\[det(A_x+A_y) = det([xA_1, yA_2]) = xy \cdot det(A).\]

Jeżeli zaszyfrujemy macierze $A_x$ i $A_y$, dostaniemy wynik działania wymnożony przez wyznacznik $det(A)$, nie wiedząc jakie działanie zostało wykonane: dodawanie, mnożenie, a może bardziej skomplikowane działanie na współczynnikach.

Szyfrowanie macierzy

Załóżmy, że szyfrujemy macierz poprzez wymnożenie przez losowe odwracalne macierze: $A \rightarrow RAS$ (tak jak w poście o szyfrowaniu macierzy). Jak zachowują się wyznaczniki? Zauważmy, że:

\[det(RAS) = det(R) \cdot det(A) \cdot det(S) = (det(R) \cdot det(S)) \cdot det(A).\]

Łatwo dobrać macierze takie, że $det(RAS) = det(A)$ (losować macierze o wyznaczniku 1, bądź unormować  mnożąc jedną przez skalar). Załóżmy dodatkowo, że w macierzach zakodowaliśmy pewne działanie f(x,y). Wyznacznik sumy macierzy ma postać:

\[det(RA_xS + RA_yS) = det(R(A_x+A_y)S) = det(A_x+A_y) = f(x,y) \cdot det(A).\]

Osoba mającą dostęp do zaszyfrowanych macierzy $RA_xS$, $RA_yS$ oraz wyznacznika $det(A)$, może dodać zaszyfrowane macierze i przemnożyć je przez odwrotność wyznacznika $det(A)^{-1}$ - w ten sposób pozna wartość funkcji $f(x,y)$.

Szyforwanie macierzy nad pierścieniem wielomianów

Pierścień wielominaów jest przemienny, więc można rozważać macierze nad nim z wyznacznikami zdefiniowanymi jak wyżej. Zaproponowane szyfrowanie jest na pewno dobre dla pierścieni wielomianów, które są izomorficzne z ciałem skończonym, na przykład dla pierścienia $R = \mathbb{Z}_q[x]/(x^p-x-1)$, gdzie $p$ i $q$ są liczbami pierwszymi (jak w NTRU Prime). W wyniku dodania dwóch zaszyfrowanych macierzy dostaniemy zaszyfrwane wielomiany:

\[f(r_1(x),r_2(x)) \cdot det(A) = f(r_1(x),r_2(x)) \cdot a(x),\]

gdzie $det(A) = a(x)$ jest pewnym ustalonym wielomianem. W tym przypadku wynikiem jest funkcja.

Wyznaczniki nad pierścieniami nieprzemiennymi?

Można też rozpatrywać wyznaczniki macierzy nad pierścieniem macierzy, ale ten jest nieprzemienny…

Literatura

[1] Linear Algebra over Commutative Rings - Bernard R. McDonald