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

20

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.

Phillip Mates
źródło
Interesująca może być również odpowiedź arnaba na moje pytanie: cstheory.stackexchange.com/questions/36/…
Suresh Venkat,
Oto działająca implementacja: wisdom.weizmann.ac.il/~neko/MAE-offline.html
Diego de Estrada

Odpowiedzi:

19

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 .

Boaz Barak
źródło
Dzięki za dobrze napisaną odpowiedź / przegląd. Przejrzałem artykuł TRNG, który napisałeś z Shaltiel i Tromer. Wygląda całkiem obiecująco. Zastanawiałem się, czy strona internetowa gazety (i kod implementacyjny) jest dostępna gdziekolwiek, ponieważ cytowany link ( people.csail.mit.edu/tromer/trng ) w gazecie nie zawiera żadnych informacji na jej temat.
Phillip Mates,
6

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.

MS Dousti
źródło
1
Dzięki za sugestię skrótu i ​​linki. W linkach nie widziałem żadnej wzmianki o osobach próbujących wdrożyć ekstraktory. Jestem bardzo ciekawy, czy próbuje się tego dokonać. Większość artykułów na temat ekstraktorów, które przeczytałem, wspomina o praktycznych zastosowaniach ekstraktorów, ale nie zawiera odniesienia do jakichkolwiek prób implementacji. Powiedziano mi, że uniknęliśmy funkcji haszujących, ponieważ nie są one przypadkowo przypadkowe, co jest bardzo przydatne w dziedzinie symulacji MC, ponieważ pseudo-RNG czasami wykazywały niedokładne wyniki [ref: prl. aps.org/abstract/PRL/v69/i23/p3382_1 ]
Phillip Mates
4

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
PulpSpy
źródło
3

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.

Nagi
źródło