Siłę szyfru można określić, oceniając jego odporność na ataki przeprowadzane jedynie od strony technicznej (czyli z pominięciem błędów powodowanych przez człowieka używającego ten szyfr). Zapewnianie przez szyfr całkowitego bezpieczeństwa jest najwyższym stopniem zabezpieczenia, jakie można zdefiniować. W rzeczywistości, zwykle używane jest pojęcie bezpieczeństwa semantycznego, które określa warunki dla zagwarantowania praktycznego bezpieczeństwa szyfru.
Całkowite bezpieczeństwo
Szyfr OTP jest jedynym znanym szyfrem, który zapewnia całkowite bezpieczeństwo.
Bezpieczeństwo semantyczne
Każdy (PPTA), który otrzymuje zaszyfrowany przy użyciu szyfru semantycznie bezpiecznego tekst danej wiadomości oraz długość tej wiadomości nie może określić żadnych dodatkowych informacji o oryginalnej wiadomości z prawdopodobieństwem (ang. non-negligibly) większym niż wszystkie inne algorytmy PPTA, które otrzymują jedynie długość oryginalnej wiadomości i nie mają dostępu do tekstu zaszyfrowanego.
Można wykazać, że szyfr OTP jest semantycznie bezpieczny, o ile używa całkowicie losowego klucza szyfrującego. Podobnie, każdy szyfr strumieniowy może posiadać tę własność, pod warunkiem, że wykorzystywany w nim generator pseudolosowy jest bezpieczny.
Wielkość zaniedbywalna - przyjmuje się, że wielkość e jest:
- niezaniedbywalna, jeżeli e >= 1/230 (w praktyce prawdopodobnie zdarzy się w 1GB danych)
- zaniedbywalna, jeżeli e <= 1/280 (w praktyce nie zdarzy się w czasie życia klucza)
Probabilistyczny algorytm o złożoności wielomianowej (ang. probabilistic, polynomial-time algorithm - PPTA) to niedeterministyczny algorytm o wielomianowej złożoności obliczeniowej, z prawdopodobieństwem błędu mniejszym niż 0.5 dla wszystkich jego wywołań.