Czy prowadzone są obecnie badania nad wdrożeniem ekstraktorów losowości?

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.

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 .

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.

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:

• Zakłada, że ​​blockcipher to permutacja losowo psuedo
• Musi być kluczowany prawdziwie losowym (ale niekoniecznie tajnym) kluczem, którego można użyć ponownie
• Jeżeli wyjściem jest m bitów, wejście musi mieć co najmniej 2m bity min-entropii
• Długość bloku i długość klucza muszą być takie same (więc jeśli używasz AES, oznacza to, że działa tylko AES-128)
• Długość wejściowa jest ograniczona, ale granica jest wysoka

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.