Funkcja jednokierunkowa – funkcja, 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 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.