Funkcja jednokierunkowa

Funkcja jednokierunkowafunkcja, która jest łatwa do wyliczenia, ale trudna do odwrócenia. „Łatwa do wyliczenia” oznacza tu, że istnieje algorytm wielomianowy, który ją wylicza. „Trudna do odwrócenia” oznacza, że żaden wielomianowy algorytm probabilistyczny nie potrafi znaleźć elementu przeciwobrazu z prawdopodobieństwem większym niż zaniedbywalne, jeśli jest wybrane losowo. Trudność dotyczy zatem średniego przypadku, a nie pesymistycznego, jak w większości problemów w teorii złożoności obliczeniowej (np. w problemach NP-trudnych).

Formalna definicja

edytuj

Formalnie funkcje jednokierunkowe definiuje się na dwa sposoby:

Funkcja silnie jednokierunkowa to funkcja   taka, że:
  •   jest obliczalna w czasie wielomianowym
  • Dla dowolnego   i dowolnego wielomianowego algorytmu probabilistycznego   jeśli   jest wystarczająco duże, to:
Pr 

Innymi słowy, żaden algorytm probabilistyczny nie jest w stanie zgadnąć wartości argumentu z prawdopodobieństwem, które nie byłoby zaniedbywalnie małe.

Funkcja słabo jednokierunkowa to funkcja   taka że:
  •   jest obliczalna w czasie wielomianowym
  • Istnieje   takie że dla dowolnego wielomianowego algorytmu probabilistycznego   jeśli   jest wystarczająco duże, to:
Pr 

Innymi słowy, każdy algorytm probabilistyczny, który ją odwraca, podaje błędną wartość z prawdopodobieństwem, które nie jest zaniedbywalnie małe.

Funkcje silnie jednokierunkowe są oczywiście również słabo jednokierunkowe. Choć istnienie tych drugich wydaje się znacznie bardziej prawdopodobne, można pokazać, że jeśli istnieją funkcje słabo jednokierunkowe, to istnieją również silnie jednokierunkowe.

Istnienie funkcji jednokierunkowych

edytuj

Istnienie funkcji jednokierunkowych jest otwartym problemem w informatyce. Z faktu ich istnienia wynikałoby automatycznie, że P≠NP(inne języki), co rozstrzygałoby najsłynniejszy problem w informatyce. Implikacja w drugą stronę nie jest znana – nie wiadomo, czy z P≠NP wynikałoby automatycznie istnienie funkcji jednokierunkowych. Wiąże się to z różnicą pomiędzy rozważaniem średniego i najgorszego przypadku w tych problemach.

Istnienie tych funkcji pozwoliłoby uzyskać wiele przydatnych w kryptografii narzędzi, między innymi:

Kandydaci na funkcje jednokierunkowe

edytuj

Ponieważ do tej pory nie wiadomo, czy funkcje jednokierunkowe istnieją, w praktyce używa się kilku funkcji, które są o to podejrzewane: funkcji, dla których pomimo wysiłku wielu badaczy nie udało się znaleźć efektywnych algorytmów odwracających.

Mnożenie vs. faktoryzacja

edytuj

Mnożenie liczb naturalnych jest łatwe algorytmicznie. Z drugiej strony jeśli pomnożymy przez siebie dwie duże liczby pierwsze (np. 34 961 i 49 369, wynik mnożenia to 1 725 989 609), znalezienie ich na podstawie iloczynu może być trudne. Mnożenie może być więc funkcją słabo jednokierunkową. Na tej funkcji opiera się w dużej mierze kryptosystem RSA.

Obecnie najlepszym znanym algorytmem faktoryzacji jest GNFS, którego złożoność wynosi  

Funkcja Rabina

edytuj

Jeśli dla danego   i   wyliczymy   (mod N), to można pokazać, że znalezienie   na podstawie y jest algorytmicznie równie trudne jak faktoryzacja   Podnoszenie do kwadratu jest więc równie dobrym kandydatem na funkcję jednokierunkową jak mnożenie. Na tej funkcji oparty jest kryptosystem Rabina.

Potęgowanie vs. logarytm dyskretny

edytuj

Jeśli dla danej liczby pierwszej   oraz   i   wyliczymy  (mod p), to okazuje się, że nie znamy efektywnego algorytmu pozwalającego znaleźć właściwe   na podstawie     i   Potęgowanie w ciele skończonym jest więc kandydatem na funkcję jednokierunkową. Opiera się na nim kryptosystem ElGamal.

Inne funkcje

edytuj

Wszystkie trzy podane wyżej funkcje mogą być funkcjami jednokierunkowymi, ale wiadomo już, że można je łatwo odwracać, jeśli ma się do dyspozycji komputer kwantowy (używając Algorytmu Shora do faktoryzacji i kwantowej transformaty Fouriera do wyliczenia logarytmu dyskretnego). Istnieją inne funkcje podejrzewane o bycie funkcjami jednokierunkowymi, np. bazujące na różnych problemach NP-zupełnych. W praktyce ich bezpieczeństwo jest jednak znacznie słabiej zbadane.

Zobacz też

edytuj

Bibliografia

edytuj