Funkcja zaniedbywalna (kryptografia)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Funkcja zaniedbywalna – funkcja, która dąży do zera szybciej niż dowolny wielomian. Funkcje takie mają szczególne znaczenie w kryptografii.

Formalnie \nu: N \rightarrow R jest zaniedbywalna, jeśli dla dowolnego d istnieje m takie, że \forall n > m zachodzi |\nu(n)| < n^{-d} .

Przykładami takich funkcji są np. f(n) = 2-n i f(n) = n-log n.

Funkcje zaniedbywalne są używane do określania bezpieczeństwa algorytmów i protokołów kryptograficznych. Przykładowo możemy powiedzieć, że szyfr jest bezpieczny, jeśli szansa odgadnięcia klucza przez osobę postronną jest zaniedbywalną funkcją długości klucza.

Definicja funkcji zaniedbywalnej jest asymptotyczna z identycznych powodów, dla których tak definiowane są złożoności algorytmów: w takiej postaci jest zamknięta na podstawowe matematyczne operacje, co umożliwia wyprowadzanie innych własności z tej definicji. W praktyce bezpieczeństwo systemów kryptograficznych wymaga ustalenia konkretnych wartości tej funkcji (np. 2-128) i użycia klucza o takiej długości, aby tę wartość uzyskać.