Czy w praktyce wykorzystywane są teoretycznie generatory pseudolosowe?

O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych gwarancji, że wyglądają pseudolosowo, powiedzmy, na wszystkie skutecznie obliczalne testy statystyczne. Jednak metody te są stosowane bez rozróżnienia we wszelkiego rodzaju aplikacjach, od protokołów kryptograficznych przez obliczenia naukowe do bankowości (prawdopodobnie). Uważam za nieco niepokojące, że nie mamy żadnej gwarancji, że aplikacje te działają zgodnie z przeznaczeniem (ponieważ każda analiza prawdopodobnie przyjęłaby prawdziwą losowość jako dane wejściowe).

Z drugiej strony, teoria złożoności i kryptografia zapewniają bardzo bogatą teorię pseudolosowości, a nawet mamy konstrukcje kandydatów na generatory pseudolosowe, które oszukałyby KAŻDY skuteczny test statystyczny, jaki można wymyślić, używając kandydujących funkcji jednokierunkowych.

Moje pytanie brzmi: czy ta teoria znalazła zastosowanie w praktyce? Mam nadzieję, że do ważnych zastosowań losowości, takich jak kryptografia lub obliczenia naukowe, używane są teoretycznie solidne PRG.

Nawiasem mówiąc, mogłem znaleźć pewną ograniczoną analizę tego, na ile popularne algorytmy, takie jak Quicksort, działają przy użyciu LSFRs jako źródła losowości i najwyraźniej działają one dobrze. Zobacz „Randomizowane algorytmy i liczby pseudolosowe” Karloffa i Raghavana .

Pojęcie „pseudolosowych generatorów„ teoretycznie rozsądnych ”nie jest tak naprawdę dobrze zdefiniowane. W końcu żaden generator pseudolosowy nie ma dowodu bezpieczeństwa. Nie wiem, czy możemy powiedzieć, że generator pseudolosowy oparty na twardości faktoryzacji dużych liczb całkowitych jest „bezpieczniejszy” niż, powiedzmy, użycie AES jako generatora pseudolosowego. (W rzeczywistości istnieje poczucie, że jest mniej bezpieczny, ponieważ znamy algorytmy faktoringu kwantowego, ale nie algorytmy kwantowe do przełamywania AES.)

Mamy dowody matematyczne dla różnych wyników kompozycji, mówiąc, że jeśli komponujesz szyfry blokowe lub funkcje skrótu w określony sposób, możesz uzyskać generatory pseudolosowe lub funkcję pseudolosową. Niektóre takie wyniki są szeroko stosowane w praktyce, np . HMAC . Ale prawdą jest, że wyniki, które osiągają PRG i zaczynają się od założenia, że ​​podstawowym składnikiem jest zwykła funkcja jednokierunkowa, nie są wystarczająco wydajne, aby można je było zastosować w aplikacjach (i jest to przynajmniej częściowo nieodłączne). Zwykle więc musimy przyjąć funkcję PRG / szyfr strumieniowy / blok-szyfr / szyfrowanie jako podstawową operację podstawową i zacząć od niej budować inne rzeczy. Problem nie dotyczy tak naprawdę analizy asymptotycznej, ponieważ zasadniczo wszystkie redukcje kryptograficzne (z wyjątkiem być może uniwersalnego PRG Levina) mogą być konkretne, a zatem dają konkretne gwarancje na podstawie konkretnych założeń.

Ale chociaż nie są one oparte na funkcjach jednokierunkowych, istnieje poczucie, że konstrukcje takie jak AES są „teoretycznie zdrowe”, ponieważ: (1) Istnieją formalne przypuszczenia na temat ich bezpieczeństwa. (2) Istnieją prace mające na celu obalenie tych przypuszczeń, a także wyciąganie z nich wniosków.

I rzeczywiście, ludzie zdają sobie sprawę, że w przypadku wielu aplikacji nie byłoby mądre stosowanie PRG, takich jak LSFR, które nie spełniają (1) i (2) powyżej.

Wygląda na to, że mylisz teorię z praktyką. Teoretycznie poprawny generator pseudolosowy jest nieodpowiedni do praktycznego zastosowania z kilku powodów:

• Jest to prawdopodobnie bardzo nieefektywne.
• Dowód bezpieczeństwa jest tylko asymptotyczny, więc dla konkretnego użytego parametru bezpieczeństwa generator pseudolosowy może być łatwy do złamania.
• Wszystkie dowody bezpieczeństwa są warunkowe, więc w pewnym sensie nawet nie spełnia pojęcia bezpieczeństwa teoretycznego.

W przeciwieństwie do tego, rzeczywiste generatory pseudolosowe są szybkie i mają różne smaki, w zależności od ich zastosowania. W przypadku zastosowań innych niż kryptograficzne, prawie wszystko inne niż zwykły LFSR wykona zadanie - nie do udowodnienia, ale w praktyce (co jest ważniejsze dla osób używających rzeczy w rzeczywistości).

Do użytku kryptograficznego ludzie starają się być mądrzejsi. W tym momencie twoja krytyka ma sens: nie możemy wiedzieć, że określony generator pseudolosowy jest „bezpieczny” i rzeczywiście niektóre stare zostały zepsute, na przykład RC4 używane w WEP. Jednak z wyżej wymienionych powodów użycie teoretycznie (warunkowo) generatora dźwięku pseudolosowego nie jest niestety realistycznym rozwiązaniem. Zamiast tego społeczność kryptologiczna polega na „wzajemnej ocenie” - innych badaczach, którzy próbują „złamać” system (ich definicja, kiedy szyfr jest uszkodzony, jest bardzo szeroka).

Wreszcie w aplikacjach, w których można zainwestować pieniądze, a bezpieczeństwo jest wystarczająco ważne - na przykład kody nuklearne - ludzie używają fizycznie generowanego hałasu (przechodzącego przez ekstraktor losowości), chociaż nawet to nie jest poza teoretyczną krytyką.

Kiedy naukowcy piszą wnioski o granty lub wstępy do artykułów, często twierdzą, że ich badania dotyczą i wspierają praktykę. Nie wiem, czy wierzą w to, czy to tylko warga (i może to zależeć od badacza), ale powinieneś zdawać sobie sprawę, że z oczywistych względów w kręgach akademickich związek jest bardzo przesadzony.

Jedną z rzeczy, która ogranicza nas jako badaczy matematycznych, jest nasze dogmatyczne przywiązanie do formalnego dowodu. Wspominasz analizę algorytmów losowych zasilanych przez proste generatory pseudolosowe. Tego rodzaju analizy nie można rozszerzyć na rzeczywiste problemy, ponieważ są one po prostu zbyt skomplikowane. A jednak w praktyce ludzie przez cały czas rozwiązują nawet problemy trudne dla NP, za pomocą świadomych metod.

Problemy w świecie rzeczywistym są lepiej rozumiane bardziej naukowym i eksperymentalnym okiem. Są one lepiej rozwiązywane z punktu widzenia inżynierii. Inspirują badania teoretyczne i od czasu do czasu są o tym informowani. Jak powiedział Dijsktra, w (teoretycznej) informatyce nie chodzi tak naprawdę o komputery, już nie.