Problem ze znalezieniem pazurów

Problem znajdowania pazurów jest klasycznym problemem teorii złożoności , mającym kilka zastosowań w kryptografii . Krótko mówiąc, mając dwie funkcje f , g , postrzegane jako wyrocznie , problem polega na znalezieniu x i y, takich jak f ( x ) = g ( y ). Para ( x , y ) jest wtedy nazywana pazurem . Niektóre problemy, zwłaszcza w kryptografii, najlepiej rozwiązuje się, gdy są postrzegane jako problem ze znalezieniem pazurów, stąd każde ulepszenie algorytmiczne rozwiązania problemu ze znalezieniem pazurów zapewnia lepszy atak na prymitywy kryptograficzne, takie jak funkcje mieszające .

Definicja

Niech $, C}$$do {\ Displaystyle f: A \ do C}$ będą skończonymi zbiorami i sol ${\ Displaystyle g: B \ do$ dwie funkcje. Para ${\ Displaystyle (x, y) \ w A \ razy B}$ nazywana jest pazurem , jeśli ${\ Displaystyle f (x) = g ( y)}$ . Problem ze znalezieniem pazura definiuje się jako znalezienie takiego pazura, jeśli taki istnieje.

Jeśli spojrzymy na funkcje losowe, spodziewamy się istnienia pazura fa , $g$${\ Displaystyle | A | \ cdot | B | \ geq | C |}$ . Dokładniej, są dokładnie ${\ Displaystyle | A | \ cdot | B|}$ pary postaci ${\ Displaystyle (x, y)}$ z ${\ Displaystyle x \ w A, y \ w B }$ ; prawdopodobieństwo, że taka para jest pazurem wynosi ${\ Displaystyle 1/|C|}$ . Więc jeśli ${\ Displaystyle | A | \ cdot | B | \ geq | C |}$ , oczekiwana liczba pazurów wynosi co najmniej 1.

Algorytmy

Jeśli używane są klasyczne komputery, najlepszy algorytm jest podobny do ataku Meet-in-the-middle , opisanego po raz pierwszy przez Diffiego i Hellmana . Algorytm działa w następujący sposób: załóż ${\ Displaystyle | A | \ równoważnik | B |}$ . Dla każdego $fa$$f(x)}$ ( $\ Displaystyle (f (x), x)}$ tabeli skrótów indeksowanej przez ${\$ . Następnie dla każdego $sol$ w górę tabeli w $\ Displaystyle g (y$ } Jeśli taki indeks istnieje, znaleźliśmy pazur. Takie podejście wymaga $|$ O $($ }

Jeśli używane są komputery kwantowe , Seiichiro Tani pokazał, że pazur można znaleźć w złożoności ${\ Displaystyle {\ sqrt [{3}] {| A | \ cdot | B|}}}$ .

Shengyu Zhang wykazał, że asymptotycznie te algorytmy są najbardziej wydajne z możliwych.

Aplikacje

Jak zauważono, większość zastosowań problemu znajdowania pazurów pojawia się w kryptografii . Przykłady obejmują:

• kolizji w kryptograficznych funkcjach skrótu .
• Ataki typu „Meet-in-the-middle” : dzięki tej technice k bitów okrągłych kluczy można znaleźć w czasie około 2 ^k/2+1 . Tutaj f szyfruje w połowie, a g odszyfrowuje w połowie. Właśnie dlatego Triple DES stosuje DES trzy razy, a nie tylko dwa.