Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości?
Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi.
Trochę kontekstu: jestem zainteresowany wykorzystaniem ekstraktorów losowości jako szybkiego źródła (prawdopodobnie?) Liczb losowych do użycia w symulacjach Monte Carlo. My (grupa ETHZ Computational Physics) stronnicze źródła o wysokiej entropii z generatorów kwantowych liczb losowych, z których chcielibyśmy wydobyć losowość. Poprzedni uczeń próbował wdrożyć konstrukcję Trevisan i napotkał problemy ze złożonością przestrzenną. Oprócz tego studenta nie znalazłem żadnego odniesienia do osób próbujących wdrożyć ekstraktory.
Uwaga: Jestem studentem CS, który jest bardzo nowy w dziedzinie teoretycznych CS i ekstraktorów losowości.
źródło
Odpowiedzi:
Znaczna część literatury na temat ekstraktorów dotyczy minimalizacji długości nasion, co jest ważne w przypadku zastosowania derandomizacji. Jednak może to nie mieć decydującego znaczenia dla twojego. Również często literatura koncentruje się na stosunkowo dużym błędzie (np. 1/100), co jest dobre w przypadku derandomizacji, ale może być problematyczne w innych ustawieniach, które wymagają wykładniczo małego błędu.
W twoim ustawieniu może być OK wygenerowanie raz na zawsze długiego losowego ziarna (powiedzmy przez rzucanie monetami), a następnie użycie go do wyodrębnienia. W takim przypadku można użyć niezależnych parami funkcji skrótu, które mają raczej wydajne implementacje. Napisałem artykuł z Shaltiel i Tromer na ten temat. Możesz także być w stanie używać prawie niezależnych funkcji skrótu, które mogą być bardziej wydajne i mieć mniejsze ziarno. (Nie znam od razu dobrego odniesienia do ich skutecznego wdrożenia, chociaż było już kilka prac nad tym.)
Jeśli masz wiele niezależnych źródeł , możesz robić lepsze rzeczy. Klasyczny ekstraktor Hadamarda działa, jeśli wskaźnik entropii jest większy niż 50% (należy o tym wspomnieć w ankietach powyżej). Jeśli entropia jest mniejsza niż 50%, mieliśmy jedną prostą konstrukcję z Impagliazzo i Wigderson . Zależność między liczbą źródeł a osiągniętym błędem od częstości entropii nie jest idealna, choć aby naprawdę to zrozumieć, trzeba przyjrzeć się dokładnym granicom określonym przez dzisiejsze twierdzenia o sumie produktów. (A jeśli chcesz założyć pewną liczbę teoretycznych przypuszczeń, możesz uzyskać jeszcze bardziej wydajne ekstraktory.) Ta konstrukcja została znacznie ulepszona na różne sposoby, z których niektóre mogą być odpowiednie dla twojego zastosowania.Teza Anup Rao .
źródło
Przede wszystkim zobacz odpowiedni temat na Wikipedii. Po drugie, możesz spojrzeć na następujący artykuł:
Ostatnie zmiany w jednoznacznych konstrukcjach ekstraktorów autorstwa Ronena Shaltiela.
Artykuł został napisany w formie ankiety i może pomóc w znalezieniu „najnowszych osiągnięć”.
Wreszcie, jeśli wszystko, czego chcesz, to ciąg bitów, który „wygląda” losowo (ale niekoniecznie jest bezpieczny kryptograficznie), możesz zastosować funkcję skrótu (taką jak MD5 lub SHA-1) do źródła o wysokiej entropii i uzyskać doskonały wynik (do eksperymentów fizycznych) w prawie żadnym momencie.
źródło
Jest też miły artykuł Dodisa, Gennaro i in. który uwzględnia praktyczne prymitywy kryptograficzne, które można wykorzystać do ekstrakcji. Pokazują, że funkcje skrótu nie są znane jako dobre ekstraktory, jednak może to być szyfr blokowy w trybie CBC-MAC (z drobnym drukiem). Rozważają również konstrukcje HMAC. Podejście to jest atrakcyjne do wdrożenia, ponieważ można używać standardowych bibliotek kryptograficznych.
W przypadku CBC-MAC „drobny druk” to w przybliżeniu:
źródło
W przypadku kryptograficznego pseudolosowego generatora możesz także zajrzeć do HKDF . W artykule omawiają ekstraktory losowości pojęciowo i praktycznie oraz podają ładne odniesienia.
Na marginesie do generowania losowości dla Monte Carlo jest oczywiście HAVEGE . Jeśli jego szybkość bitowa i „sprawdzalność” są wystarczające, możesz uniknąć konieczności marnowania czasu na generatory kwantowe.
źródło