Prouver la sécurité du générateur de nombres pseudo-aléatoires Nisan-Wigderson

13

Soit S={Si}1in une conception partielle (m,k) et f:{0,1}m{0,1} une fonction booléenne. Le générateur de Nisan-Wigderson Gf:{0,1}l{0,1}n est défini comme suit:

Gf(x)=(f(x|S1),,f(x|Sn))

Pour calculer le ème bit de G f, nous prenons les bits de x avec des index dans S i puis nous leur appliquons f .iGfxSif

Supposons que est 1f -hard pour les circuits de taillenccest une constante. Comment prouver queGfest(nc1ncnccGfgénérateur de nombres pseudo-aléatoires sûrs?(nc2,2nc)

Définitions:

Une conception partielle est un ensemble de sous-ensembles S 1 , , S n[ l ] = { 1 , , l } tels que(m,k)S1,,Sn[l]={1,,l}

  • pour tout : | S i | = m , eti|Si|=m
  • pour tout : | S iS j | k .ij|SiSj|k

Une fonction est - ε -hard pour les circuits de taille s IFF pas de circuit de taille s peut prédire f avec une probabilité ε mieux qu'un tirage au sort pièce.fϵssfϵ

Une fonction est ( s , e ) -secure générateur de nombres pseudo-aléatoires ssi pas de circuit de taille s peut distinguer entre un nombre aléatoire et un nombre généré par G f avec probabilité meilleure que ϵ .G:{0,1}l{0,1}n(s,ϵ)sGfϵ

Nous utilisons pour la chaîne composée de x bits S » avec les index de A .x|AxA

Kaveh
la source
ps: ce n'est pas vraiment mes devoirs mais s'il vous plaît traitez-le comme vous traiteriez une question de devoirs, il est parfois donné aux étudiants prenant une introduction au cours de crypto.
Kaveh
3
et que la bataille CS.SE contre crypto.SE commence! (:
Ran G.
1
google donne de très bons résultats: 1 , 2
Ran G.
Ce n'est pas une bonne réponse - c'est seulement une recherche google. Vous souhaitez peut-être y répondre?
Ran G.
@RanG., Bon point.
Kaveh

Réponses:

1

Voici la réponse de Ran G. mentionnée dans les commentaires: Google donne de très bons résultats: 1 , 2 .

Yuval Filmus
la source