Was ist die Motivation hinter der Definition von Pseudozufall in Nisan / Wigderson?

Ich lese den Klassiker "Hardness vs Randomness" von Nisan und Wigderson. Sei und fixiere eine Funktion . Sie definieren eine Familie von Funktionen , die für jeden Stromkreis der Größe pseudozufällig sindL : N → N G = { G n : B L ( n ) → B n$B=\{0,1\}$$l\colon \mathbb{N} \to \mathbb{N}$$G = \{G_n : B^{l(n)} \to B^n\}$$n$

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(wobei einheitliche Zufallsvariablen sind).$x \in B^{n},y \in B^{l(n)}$

Ich verstehe, dass ich und als Zufallsvariablen betrachten und den Abstand zwischen und als Zufallsvariablen vergleichen möchte . Ich habe die Intuition, dass Schaltkreise als eine Art "Test" verwendet werden, um zu sehen, ob "herausgefunden" werden kann. Ich habe wirklich Probleme damit, warum die Bedingung die richtige ist. Hat jemand einen Rat, wie man an diese Definition denkt?y x G ( y ) G ( ∗ $x$$y$$x$$G(y)$$G$$(*)$

Es gibt zwei Aspekte, die erwähnt werden müssen.

Die erste ist die allgemeine Idee, eine PRG zu definieren, indem ihre Ausgabe anders aussieht als bei kleinen Schaltkreisen einheitlich . Diese Idee geht auf Yao zurück und ist wirklich die bestmögliche Definition, die Sie verlangen können, wenn Sie explizit auf Pseudozufälligkeit für rechnergebundene Beobachter abzielen .

Der zweite Aspekt ist die Auswahl von Parametern, bei denen wir die Schaltungsgröße auf und die Akzeptanzwahrscheinlichkeitsdifferenz auf begrenzen , wobei auch die PRG-Ausgangsgröße ist. Diese Wahl unterscheidet sich etwas von der üblichen Krypto-Wahl, bei der die Schaltungsgröße und die Wahrscheinlichkeitsdifferenz kleiner sein muss als bei jeder . In unserem Fall spezifische Parameter (anstelle von1 / n n p o l y ( n ) p o l y ( n ) p o l y ( n ) L ( n ) $n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) wurden benötigt, um die genauesten Ergebnisse zu erzielen, einschließlich insbesondere von Polynomsimulationen. Während man im Prinzip 3 verschiedene Parameter haben kann, stellte sich heraus, dass unsere Ergebnisse im Wesentlichen auf die gleiche Weise funktionierten, so dass wir sie zu einem einzigen falteten (zusätzlich zu der Eingabegröße die als Funktion von angesehen wurde ).$l(n)$$n$

Ich bin auf keinen Fall ein Experte auf diesem Gebiet, aber eine Schlüsselkomponente der Definition von Pseudozufälligkeit (im Gegensatz zu Versuchen, Zufälligkeit zu definieren) ist, dass das Ziel von etwas "Pseudozufälligem" darin besteht, eine Schaltung zu täuschen. Mit anderen Worten, die Motivation besteht darin, an die Pseudozufallskette zu denken, die der Schaltung zugeführt wird, anstatt an die wirklich zufällige Kette.

In diesem Sinne ist es nicht wirklich so, als würden und "gleich aussehen". Es ist so, dass sie für eine Schaltung (von notwendigerweise begrenzter Komplexität) "gleich aussehen" .G ( y $x$$G(y)$

Die Rolle der Schaltung ist also entscheidend, anstatt nur eine "Testfunktion" zu sein.

Hoffentlich kann ich die Antwort von Suresh ein wenig erläutern. Erstens glaube ich nicht , dass die Strenge der Ungleichheit in Ihrem benötigt wird , und ich bin auch nicht sicher , warum 1 / n erforderlich ist, und nicht 1 / 2 n oder etwas anderes. In der Praxis denke ich jedoch, dass 1 / n ausreicht, um einige interessante theoretische Ergebnisse zu erzielen.$(*)$$1/n$$1/2n$

Aber dann möchten Sie mit ziemlicher Sicherheit behaupten, dass jedes in einer gewissen Zeit berechenbar ist, etwa exponentiell. Ich denke, Sie müssen außerdem behaupten, dass l ( n ) < n ist . Sie können sich l ( n ) als die Samenlänge vorstellen. Somit ist G i pseudozufällig, wenn es die Anzahl der Bits in einer zufälligen Folge der Länge l ( n ) erhöhen kann, ohne von einer Schaltung mit einer Größe von weniger als n erfasst zu werden .$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$