Quelle est la motivation derrière la définition du pseudo-aléatoire dans Nisan / Wigderson?

Je lis le classique "Hardness vs Randomness" de Nisan et Wigderson. Soit , et fixer une fonction l : N → N . Ils définissent une famille de fonctions G = { G n : B l ( n ) → B n } pour être pseudo-aléatoires dans le cas pour chaque circuit de taille n que nous avons$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$

(où sont des variables aléatoires uniformes).$x \in B^{n},y \in B^{l(n)}$

Je comprends que je dois considérer et y comme des variables aléatoires et que je veux comparer la distance entre x et G ( y ) comme des variables aléatoires. J'ai l'intuition que les circuits sont utilisés comme une sorte de "tests" pour voir si G peut être "compris". Ce avec quoi je lutte vraiment, c'est pourquoi la condition ( ∗ ) est la bonne. Quelqu'un a-t-il des conseils sur la façon de penser à cette définition?$x$$y$$x$$G(y)$$G$$(*)$

Il y a deux aspects qui doivent être mentionnés.

Le premier est l'idée générale de définir un PRG en ayant un aspect différent de celui de l'uniforme aux petits circuits . Cette idée remonte à Yao et est vraiment la définition la plus forte possible que vous pouvez demander lorsque vous visez explicitement le pseudo-aléatoire pour les observateurs liés au calcul .

Le deuxième aspect est le choix des paramètres où nous limitons la taille du circuit à et la différence de probabilité d'acceptation à 1 / n , où n est également la taille de sortie PRG. Ce choix est quelque peu différent de celui de la crypto habituelle où la taille du circuit est p o l y ( n ) et la différence de probabilité doit être inférieure à tout p o l y ( n ) . Dans notre cas, des paramètres spécifiques (plutôt que p o l y ( n $n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) étaient nécessaires pour obtenir les résultats les plus étroits, notamment des simulations polynomiales. Alors qu'en principe, on pouvait avoir 3 paramètres différents, il s'est avéré que nos résultats fonctionnaient essentiellement de la même manière, nous les avons donc pliés en un seul (en plus de la taille d'entrée qui était considérée comme une fonction de n ).$l(n)$$n$

Je ne suis nullement un expert en la matière, mais un élément clé de la définition du pseudo-aléatoire (par opposition aux tentatives de définir le hasard) est que le but de quelque chose de "pseudo-aléatoire" est de tromper un circuit. En d'autres termes, la motivation est de penser que la chaîne pseudo-aléatoire est fournie au circuit au lieu de la chaîne véritablement aléatoire.

En ce sens, ce n'est pas vraiment que vous essayez de prétendre que et G ( y ) "se ressemblent". C'est qu'ils "se ressemblent" à un circuit (de complexité nécessairement bornée).$x$$G(y)$

Le rôle du circuit est donc crucial, au lieu d'être simplement une "fonction de test".

$(*)$$1/n$$1/2n$

$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$