Funkcja zaniedbywalna (kryptografia)

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⁻¹²⁸) i użycia klucza o takiej długości, aby tę wartość uzyskać.