Czy asymptotyczne dolne granice są istotne dla kryptografii?

Ogólnie uważa się, że asymptotyczna dolna granica, taka jak twardość wykładnicza, sugeruje, że problem jest „z natury trudny”. Uważa się, że szyfrowanie „z natury trudne do złamania” jest bezpieczne.

Jednak asymptotyczna dolna granica nie wyklucza możliwości, że ogromna, ale skończona klasa wystąpień problemów jest łatwa (np. Wszystkie wystąpienia o rozmiarze mniejszym niż ).$10^{1000}$

Czy jest jakikolwiek powód, by sądzić, że kryptografia oparta na asymptotycznych dolnych granicach zapewni jakiś szczególny poziom bezpieczeństwa? Czy eksperci ds. Bezpieczeństwa rozważają takie możliwości, czy są po prostu ignorowani?

Przykładem jest użycie funkcji klapy w oparciu o rozkład dużych liczb na ich czynniki pierwsze. W pewnym momencie uważano to za z natury trudne (myślę, że wykładnicza była hipoteza), ale teraz wielu uważa, że ​​może istnieć algorytm wielomianowy (tak jak w przypadku testowania pierwotności). Wydaje się, że nikomu nie zależy na braku wykładniczej dolnej granicy.

Uważam, że zaproponowano inne funkcje drzwi pułapkowych, które są uważane za trudne NP (patrz powiązane pytanie ), a niektóre mogą nawet mieć udowodnioną dolną granicę. Moje pytanie jest bardziej fundamentalne: czy ma znaczenie, czym jest asymptotyczna dolna granica? Jeśli nie, to czy praktyczne bezpieczeństwo jakiegokolwiek kodu kryptograficznego jest w ogóle związane z jakimkolwiek wynikiem asymptotycznej złożoności?

Spróbuję udzielić częściowej odpowiedzi, ponieważ nie jestem w pełni świadomy tego, jak ten problem jest rozpatrywany przez całą społeczność kryptograficzną (może repost na crypto.SE ?).

Powiedziałbym, że istnieją dwa „rodzaje” kryptografów: teoretyczny i praktyczny . Nie będę próbował ich rozróżniać (każdy praktyczny kryptograf jest również trochę teoretykiem ...), ale powiem to w przypadku kryptografii teoretycznej - ten problem nie ma tak naprawdę znaczenia. Dla każdego parametru bezpieczeństwa będzie istniał rozmiar instancji, który zapewni ten poziom bezpieczeństwa, i zwykle to wszystko, na czym nam zależy.

$2^{1024}$

A concrete example I can think of is the discrete log or the DDH assumption (the security of many cryptographic schemes are based on these assumptions). We assume that for some group $G$ computing the log takes $O(|G|)$ time. (We can't be sure: it might be that $\text{P}=\text{NP}$ and this problem can be solved in $O(\log |G|)$). Cryptographers DO care about the actual time it takes to compute the log. More accurately, they care alot about special cases for which computing the log is easy. In many papers you will see the sentence "Let $G$ be a group in which DDH is hard". See this survey for families of groups for which DDH is believed to be intractable (unless P=NP).