Kryptografia neuronowa

Kryptografia neuronowa jest gałęzią kryptografii zajmującą się analizą zastosowania algorytmów stochastycznych , zwłaszcza algorytmów sztucznych sieci neuronowych , do zastosowania w szyfrowaniu i kryptoanalizie .

Definicja

Sztuczne sieci neuronowe są dobrze znane ze swojej zdolności do selektywnego eksplorowania przestrzeni rozwiązań danego problemu. Cecha ta znajduje naturalną niszę zastosowania w dziedzinie kryptoanalizy . Jednocześnie sieci neuronowe oferują nowe podejście do atakowania algorytmów szyfrujących, oparte na zasadzie, że każda funkcja może zostać odtworzona przez sieć neuronową, która jest potężnym, sprawdzonym narzędziem obliczeniowym, które można wykorzystać do znalezienia funkcji odwrotnej dowolnej funkcji kryptograficznej. algorytm.

Idee wzajemnego uczenia się, samouczenia się i stochastycznego zachowania sieci neuronowych i podobnych algorytmów mogą być wykorzystywane w różnych aspektach kryptografii, takich jak kryptografia klucza publicznego , rozwiązywanie problemu dystrybucji kluczy za pomocą wzajemnej synchronizacji sieci neuronowych, haszowania lub generowania pseudo- liczby losowe .

Innym pomysłem jest zdolność sieci neuronowej do rozdzielania przestrzeni na nieliniowe elementy za pomocą „odchylenia”. Daje różne prawdopodobieństwa aktywacji lub nie aktywacji sieci neuronowej. Jest to bardzo przydatne w przypadku kryptoanalizy.

Do zaprojektowania tej samej dziedziny badań używa się dwóch nazw: Neuro-Cryptography i Neural Cryptography.

Pierwsza znana praca na ten temat pochodzi z 1995 roku w pracy magisterskiej z informatyki.

Aplikacje

W 1995 roku Sebastien Dourlens zastosował sieci neuronowe do kryptoanalizy DES , umożliwiając sieciom nauczenie się odwracania tablic S DES. Podkreślono stronniczość w DES badaną za pomocą kryptografii różnicowej przeprowadzonej przez Adi Shamira . Eksperyment pokazuje, że można znaleźć około 50% bitów klucza, co pozwala na znalezienie całego klucza w krótkim czasie. Zaproponowano zastosowanie sprzętu z wieloma mikrokontrolerami ze względu na łatwą implementację wielowarstwowych sieci neuronowych w sprzęcie.
Jeden przykład protokołu klucza publicznego podaje Khalil Shihab. Opisuje schemat deszyfrowania i tworzenia klucza publicznego w oparciu o sieć neuronową ze wsteczną propagacją . Schemat szyfrowania oraz proces tworzenia klucza prywatnego są oparte na algebrze Boole'a. Zaletą tej techniki jest niewielka złożoność czasowa i pamięciowa. Wadą jest właściwość algorytmów propagacji wstecznej: ze względu na duże zbiory uczące faza uczenia sieci neuronowej jest bardzo długa. Dlatego użycie tego protokołu jest jak dotąd tylko teoretyczne.

Protokół wymiany kluczy neuronowych

Najczęściej używanym protokołem wymiany kluczy między dwiema stronami A i B w praktyce jest protokół wymiany kluczy Diffie-Hellman . Bezpiecznym zamiennikiem tej metody powinna być wymiana kluczy neuronowych, która opiera się na synchronizacji dwóch maszyn z parzystością drzewa. Synchronizacja tych dwóch maszyn jest podobna do synchronizacji dwóch chaotycznych oscylatorów w komunikacji chaosu .

Maszyna parzystości drzewa

Maszyna parzystości drzewa

Maszyna parzystości drzewa jest specjalnym rodzajem wielowarstwowej sieci neuronowej z wyprzedzeniem .

Składa się z jednego neuronu wyjściowego, K neuronów ukrytych i K × N neuronów wejściowych. Wejścia do sieci przyjmują trzy wartości:

${\ Displaystyle x_ {ij} \ w \ lewo \ {-1,0, + 1 \ prawo \}}$

Wagi między neuronami wejściowymi i ukrytymi przyjmują wartości:

${\ Displaystyle w_ {ij} \ w \ lewo \ {- L, ..., 0, ..., + L \ w prawo \}}$

Wartość wyjściowa każdego neuronu ukrytego jest obliczana jako suma wszystkich multiplikacji neuronów wejściowych i tych wag:

${\ Displaystyle \ sigma _ {i} = \ operatorname {sgn} (\ suma _ {j = 1} ^ {N} w_ {ij} x_{ij})}$

Signum to prosta funkcja, która zwraca −1,0 lub 1:

${\ Displaystyle \ operatorname {sgn} (x) = {\ rozpocząć {przypadki} -1 i {\ tekst {jeśli}} x<0,\\0&{\text{if }}x=0,\\1&{\text{if }}x>0.\end{przypadki}}}$

Jeśli iloczyn skalarny wynosi 0, wyjście ukrytego neuronu jest odwzorowywane na −1, aby zapewnić binarną wartość wyjściową. Wyjście sieci neuronowej jest następnie obliczane jako iloczyn wszystkich wartości tworzonych przez ukryte elementy:

${\ Displaystyle \ tau = \ prod _ {i = 1} ^ {K} \ sigma _ {i}}$

Dane wyjściowe maszyny parzystości drzewa są binarne.

Protokół

Każda strona ( A i B ) używa własnej maszyny parzystości drzewa. W tych krokach osiąga się synchronizację maszyn parzystości drzewa

1. Zainicjuj losowe wartości wagi
2. Wykonuj te kroki, aż do osiągnięcia pełnej synchronizacji
   1. Wygeneruj losowy wektor wejściowy X
   2. Oblicz wartości ukrytych neuronów
   3. Oblicz wartość neuronu wyjściowego
   4. Porównaj wartości obu maszyn parzystości drzewa
      1. Wyniki są takie same: do wag stosowana jest jedna z odpowiednich reguł uczenia się
      2. Wyjścia są różne: przejdź do 2.1

Po osiągnięciu pełnej synchronizacji (wagi wij _obu maszyn parzystości drzewa są takie same), A i B mogą używać swoich wag jako kluczy. Ta metoda jest znana jako uczenie dwukierunkowe. Do synchronizacji można użyć jednej z następujących reguł uczenia się:

• Hebbowska zasada uczenia się:

${\ Displaystyle w_ {i} ^ {+} = g (w_ {i} + \sigma _{i}x_{i}\Theta (\sigma _{i}\tau )\Theta (\tau ^{A}\tau ^{B}))} Antyhebbowska reguła uczenia$

• :

${\ Displaystyle w_ {i} ^ {+} = g (w_ {i} - \ sigma _ {i} x_ {i} \ Theta (\ sigma _ {i}\tau )\Theta (\tau ^{A}\tau ^{B})}}$

• Błądzenie losowe:

${\ Displaystyle w_ {i} ^ {+} = g (w_ {i} + x_ {i} \ Theta (\ sigma _ {i} \ tau) \ Theta (\ tau ^ {A} \ tau ^ {B} ))}$

Gdzie:

${\ Displaystyle \ Theta (a, b) = 0}$ jeśli ${\ Displaystyle a \ neq b}$ w przeciwnym razie ${\ Displaystyle \ Theta (a, b )=1}$

I:

$\ Displaystyle g (x)}$${\ Displaystyle \ {-L, -L + 1, ..., 0, ..., L-1, L \}}$ jest funkcją , $L$ utrzymuje w

Ataki i bezpieczeństwo tego protokołu

W każdym ataku bierze się pod uwagę, że atakujący E może podsłuchiwać wiadomości między stronami A i B , ale nie ma możliwości ich zmiany.

Brutalna siła

Aby przeprowadzić atak brute force, atakujący musi przetestować wszystkie możliwe klucze (wszystkie możliwe wartości wag wij). Przez K neuronów ukrytych, K × N neuronów wejściowych i granicę wag L , daje to (2L+1) ^KN możliwości. Na przykład konfiguracja K = 3, L = 3 i N = 100 daje nam 3*10 ²⁵³ kluczowych możliwości, uniemożliwiając atak przy dzisiejszej mocy komputera.

Nauka z własną maszyną parzystości drzewa

Jeden z podstawowych ataków może zostać przeprowadzony przez atakującego, który posiada tę samą maszynę parzystości drzewa, co strony A i B. Chce zsynchronizować swoją maszynę parzystości drzewa z tymi dwoma stronami. W każdym kroku możliwe są trzy sytuacje:

1. Wynik(A) ≠ Wynik(B): Żadna ze stron nie aktualizuje swoich wag.
2. Wyjście (A) = Wyjście (B) = Wyjście (E): Wszystkie trzy strony aktualizują wagi w swoich maszynach parzystości drzewa.
3. Wyjście (A) = Wyjście (B) ≠ Wyjście (E): Strony A i B aktualizują swoje maszyny parzystości drzewa, ale atakujący nie może tego zrobić. Z tego powodu jego nauka jest wolniejsza niż synchronizacja stron A i B.

Udowodniono, że synchronizacja dwóch stron jest szybsza niż poznanie atakującego. Można to poprawić zwiększając głębokość synaptyczną L sieci neuronowej. Daje to temu protokołowi wystarczające bezpieczeństwo, a osoba atakująca może znaleźć klucz tylko z niewielkim prawdopodobieństwem.

Inne ataki

W przypadku konwencjonalnych systemów kryptograficznych możemy poprawić bezpieczeństwo protokołu poprzez zwiększenie długości klucza. W przypadku kryptografii neuronowej ulepszamy ją zwiększając głębokość synaptyczną L sieci neuronowych. Zmiana tego parametru wykładniczo zwiększa koszt udanego ataku, podczas gdy wysiłek użytkowników rośnie wielomianowo. Dlatego złamanie zabezpieczeń wymiany kluczy neuronowych należy do klasy złożoności NP.

Alexander Klimov, Anton Mityaguine i Adi Shamir twierdzą, że pierwotny schemat synchronizacji neuronowej można złamać co najmniej trzema różnymi atakami — analizą geometryczną, probabilistyczną i algorytmami genetycznymi. Mimo że ta konkretna implementacja nie jest bezpieczna, idee stojące za chaotyczną synchronizacją mogą potencjalnie prowadzić do bezpiecznej implementacji.

Maszyna parzystości permutacji

Maszyna parzystości permutacji jest binarnym wariantem maszyny parzystości drzewa.

Składa się z jednej warstwy wejściowej, jednej warstwy ukrytej i jednej warstwy wyjściowej. Liczba neuronów w warstwie wyjściowej zależy od liczby jednostek ukrytych K. Każdy neuron ukryty ma N neuronów wejścia binarnego:

${\ Displaystyle x_ {ij} \ w \ lewo \ {0,1 \ prawo \}}$

Wagi między neuronami wejściowymi i ukrytymi są również binarne:

${\ Displaystyle w_ {ij} \ w \ lewo \ {0,1 \ prawo \}}$

Wartość wyjściowa każdego neuronu ukrytego jest obliczana jako suma wszystkich dysjunkcji wyłącznych (wyłącznych lub) neuronów wejściowych i tych wag:

${\ Displaystyle \ sigma _ {i} = \ teta _ {N} (\ suma _ {j = 1} ^ {N} w_ { ij}\oplus x_{ij})}$

(⊕ oznacza XOR).

Funkcja jest funkcją progową, która zwraca 0 lub 1: ${\ Displaystyle \ theta _ {N} (x)}$

${\ Displaystyle \ teta _ {N} (x) = {\ rozpocząć {przypadki} 0 i {\ tekst {jeśli}} x \leq N/2,\\1&{\text{if }}x>N/2.\end{przypadki}}}$

Wyjście sieci neuronowej z dwoma lub więcej ukrytymi neuronami można obliczyć jako wyłączność lub wartości wytwarzane przez ukryte elementy:

${\ Displaystyle \ tau = \ bigoplus _ {i = 1} ^ {K} \ sigma _ {i}}$

Możliwe są również inne konfiguracje warstwy wyjściowej dla K>2.

Ta maszyna okazała się wystarczająco odporna na niektóre ataki, więc może być używana jako środek kryptograficzny, ale wykazano, że jest podatna na atak probabilistyczny.

Ochrona przed komputerami kwantowymi

Komputer kwantowy to urządzenie wykorzystujące mechanizmy kwantowe do obliczeń. W tym urządzeniu dane są przechowywane w postaci kubitów (kwantowych cyfr binarnych). Daje to komputerowi kwantowemu w porównaniu z komputerem konwencjonalnym możliwość rozwiązywania skomplikowanych problemów w krótkim czasie, np. problemu logarytmu dyskretnego czy faktoryzacji. Algorytmy, które nie są oparte na żadnym z tych problemów teorii liczb, są poszukiwane ze względu na tę właściwość.

Protokół wymiany kluczy neuronowych nie jest oparty na żadnej teorii liczb. Opiera się na różnicy między jednokierunkową i dwukierunkową synchronizacją sieci neuronowych. Dlatego coś takiego jak neuronowy protokół wymiany kluczy może prowadzić do potencjalnie szybszych schematów wymiany kluczy.

Zobacz też

• Sieć neuronowa
• Stochastyczna sieć neuronowa
• Algorytm Shora

• Neuro-Cryptography 1995 - Pierwsza definicja neuro-kryptografii (AI Neural-Cryptography) zastosowana do kryptografii DES przez Sebastiena Dourlensa we Francji.
• Kryptografia neuronowa - Opis jednego rodzaju kryptografii neuronowej na Uniwersytecie w Würzburgu w Niemczech.
• Kinzel, W.; Kanter, I. (2002). „Kryptografia neuronowa”. Materiały z 9. Międzynarodowej Konferencji na temat Przetwarzania Informacji Neuronowych . ICONIP '02. s. 1351–1354. arXiv : cond-mat/0208453 . doi : 10.1109/ICONIP.2002.1202841 . - Jeden z wiodących artykułów wprowadzających koncepcję wykorzystania zsynchronizowanych sieci neuronowych do uzyskania systemu uwierzytelniania klucza publicznego.
•    Li, Li-Hua; Lin, Luon-Chang; Hwang, Min-Shiang (listopad 2001). „Schemat zdalnego uwierzytelniania hasła dla architektury wieloserwerowej z wykorzystaniem sieci neuronowych”. Transakcje IEEE w sieciach neuronowych . 12 (6): 1498–1504. doi : 10.1109/72.963786 . ISSN 1045-9227 . PMID 18249979 . - Możliwości praktycznego zastosowania kryptografii neuronowej.
•   Klimow, Aleksander; Mityagin, Anton; Szamir, Adi (2002). „Analiza kryptografii neuronowej” (PDF) . Postępy w kryptologii . ASIACRYPT 2002. LNCS . Tom. 2501. s. 288–298. doi : 10.1007/3-540-36178-2_18 . ISSN 0302-9743 . Źródło 2017-11-15 . - Analiza kryptografii neuronowej w ogólności i skupienie się na słabościach i możliwych atakach wykorzystania zsynchronizowanych sieci neuronowych.
• Synchronizacja neuronowa i kryptografia - Andreas Ruttor. Praca doktorska, Bayerische Julius-Maximilians-Universität Würzburg, 2006.
•     Ruttor, Andreas; Kinzel, Wolfgang; Naeh, Ryfka; Kanter, Ido (marzec 2006). „Atak genetyczny na kryptografię neuronową”. Przegląd fizyczny E. 73 (3): 036121. arXiv : cond-mat/0512022 . Bibcode : 2006PhRvE..73c6121R . doi : 10.1103/PhysRevE.73.036121 . ISSN 1539-3755 . PMID 16605612 . S2CID 27786815 .
• Khalil Shihab (2006). „Sieć neuronowa ze wsteczną propagacją dla bezpieczeństwa sieci komputerowej” (PDF) . Journal of Computer Science 2 : 710–715. Zarchiwizowane od oryginału (PDF) w dniu 2007-07-12.