Wie man kryptographisch starke Sequenzen von pseudo-zufälligen Bits erzeugt

Wir geben eine Reihe von Bedingungen an, die es ermöglichen, 50–50 unvorhersehbare Bits zu erzeugen. Basierend auf diesen Bedingungen präsentieren wir ein allgemeines algorithmisches Schema zur Konstruktion von deterministischen Algorithmen in polynomialer Zeit, die einen kurzen geheimen zufälligen Eingabewert in eine lange Sequenz unvorhersehbarer pseudo-zufälliger Bits erweitern. Wir geben eine Implementierung unseres Schemas und zeigen einen pseudo-zufälligen Bit-Generator, für den jede effiziente Strategie zur Vorhersage des nächsten Ausgabebits mit einer Wahrscheinlichkeit besser als 50–50 leicht in einen „gleich effizienten“ Algorithmus zur Lösung des diskreten Logarithmusproblems umgewandelt werden kann. Insbesondere: Wenn das diskrete Logarithmusproblem nicht in probabilistischer polynomialer Zeit gelöst werden kann, kann kein probabilistischer polynomieller Algorithmus das nächste Ausgabebit besser erraten als durch Münzwurf: Wenn „Kopf“, dann „0“ raten; wenn „Zahl“, dann „1“ raten.