Gibt es aktuelle Forschungen zur Implementierung von Randomness Extractors?

Wurden Untersuchungen zur Implementierung von Zufallsextraktorkonstruktionen durchgeführt?

Es scheint, dass Extractor-Proofs Big-Oh verwenden, was die Möglichkeit für große versteckte Konstanten lässt und programmatische Implementierungen möglicherweise unrealistisch macht.

Kontext: Ich bin daran interessiert, Zufallszahlenextraktoren als schnelle Quelle für (nachweislich?) Zufallszahlen zur Verwendung in Monte-Carlo-Simulationen zu verwenden. Wir (eine Gruppe der ETHZ für Computerphysik) haben Quellen mit hoher Entropie von Quanten-Zufallszahlengeneratoren vorgespannt, aus denen wir die Zufälligkeit extrahieren möchten. Ein früherer Student versuchte, eine Trevisan-Konstruktion zu implementieren, und stieß auf räumliche Komplexitätsprobleme. Abgesehen von diesem Studenten habe ich keinen Hinweis auf Leute gefunden, die versuchen, Extraktoren zu implementieren.

Hinweis: Ich bin ein CS-Student, der in den Bereichen Theoretische CS und Zufallsextraktoren sehr neu ist.

Ein Großteil der Extraktorliteratur befasst sich mit der Minimierung der Samenlänge, was für die Anwendung bei der Derandomisierung wichtig ist. Es ist jedoch möglicherweise nicht entscheidend für Sie. Außerdem konzentriert sich die Literatur häufig auf relativ große Fehler (z. B. 1/100), was für eine Derandomisierung in Ordnung ist, in anderen Situationen jedoch problematisch sein kann, die einen exponentiell kleinen Fehler erfordern.

In Ihrer Einstellung kann es in Ordnung sein, ein für allemal einen langen zufälligen Samen zu erzeugen (z. B. durch Werfen von Münzen) und ihn dann zum Extrahieren zu verwenden. In diesem Fall könnten Sie paarweise unabhängige Hash-Funktionen verwenden, die ziemlich effizient implementiert sind. Ich habe mit Shaltiel und Tromer eine Arbeit zu diesem Thema geschrieben. Möglicherweise können Sie auch fast unabhängige Hash-Funktionen verwenden, die effizienter sind und einen kleineren Startwert haben. (Ich kenne nicht ohne weiteres eine gute Referenz für ihre effiziente Implementierung, obwohl es mehrere Arbeiten dazu gegeben hat.)

Wenn Sie mehrere unabhängige Quellen haben, können Sie bessere Dinge tun. Der klassische Hadamard-Extraktor funktioniert, wenn die Entropierate größer als 50% ist (dies sollte in den obigen Erhebungen erwähnt werden). Wenn die Entropie kleiner als 50% ist, hatten wir mit Impagliazzo und Wigderson eine einfache Konstruktion . Die Abhängigkeit zwischen der Anzahl der Quellen und dem erreichten Fehler von der Entropierate ist nicht ideal. Um dies jedoch wirklich zu verstehen, müssen Sie die genauen Grenzen betrachten, die durch die heutigen Summenproduktsätze gegeben sind. (Und wenn Sie bereit sind, bestimmte zahlentheoretische Vermutungen anzunehmen, können Sie noch effizientere Extraktoren erhalten.) Diese Konstruktion wurde auf verschiedene Weise erheblich verbessert, von denen einige für Ihre Anwendung relevant sein könnten.Anup Raos These .

Sehen Sie sich zunächst das relevante Thema auf Wikipedia an. Zweitens können Sie sich das folgende Papier ansehen:

Jüngste Entwicklungen bei expliziten Konstruktionen von Extraktoren von Ronen Shaltiel.

Das Papier ist in Form einer Umfrage verfasst und kann Ihnen helfen, die "jüngsten Entwicklungen" zu finden.

Wenn Sie nur eine Folge von Bits wünschen, die zufällig "aussieht" (aber nicht unbedingt kryptografisch sicher ist), können Sie eine Hash-Funktion (wie MD5 oder SHA-1) auf Ihre Quelle mit hoher Entropie anwenden und erhalten eine ausgezeichnetes Ergebnis (für physikalische Experimente) in fast kürzester Zeit.

Es gibt auch eine schöne Arbeit von Dodis, Gennaro et al. Dies berücksichtigt praktische kryptografische Grundelemente, die zur Extraktion verwendet werden können. Sie zeigen, dass Hash-Funktionen nicht als gute Extraktoren bekannt sind, jedoch eine Blockverschlüsselung im CBC-MAC-Modus sein kann (mit etwas Kleingedrucktem). Sie berücksichtigen auch HMAC-Konstruktionen. Der Ansatz ist für die Implementierung ansprechend, da Sie Standardkryptografiebibliotheken verwenden können.

Für CBC-MAC ist das "Kleingedruckte" ungefähr:

• Angenommen, die Blockchiffre ist eine pseudozufällige Permutation
• Muss mit einem wirklich zufälligen (aber nicht unbedingt geheimen) Schlüssel versehen sein, der wiederverwendet werden kann
• Wenn die Ausgabe m Bits beträgt, muss die Eingabe mindestens 2 m Bits Min-Entropie aufweisen
• Blocklänge und Schlüssellänge müssen identisch sein (wenn Sie AES verwenden, bedeutet dies, dass nur AES-128 funktioniert)
• Die Eingabelänge ist begrenzt, aber die Grenze ist hoch

Für den Fall eines kryptografischen Pseudozufallsgenerators können Sie sich auch an HKDF wenden . In der Arbeit diskutieren sie Zufallsextraktoren konzeptionell und praktisch und geben nette Hinweise.

Als Randnotiz zur Erzeugung von Zufälligkeit für Monte Carlo gibt es natürlich HAVEGE . Wenn die Bit-Geschwindigkeit und die "Beweisbarkeit" ausreichen, müssen Sie möglicherweise nicht mit den Quantengeneratoren herumspielen.