Qual é a motivação por trás da definição de pseudo-aleatório em Nisan / Wigderson?

16

Estou lendo o clássico "Dureza vs Aleatoriedade" de Nisan e Wigderson. Deixe e corrija a função . Eles definem uma família de funções como pseudo-aleatória no caso de cada circuito de tamanho que temosl : NN G = { G n : B l ( n )B n }B={0 0,1 1}eu:NNG={Gn:Bl(n)Bn}n

()  |P(C(x)=1)P(C(G(y))=1)|<1/n

(onde são variáveis ​​aleatórias uniformes).xBn,yBl(n)

Entendo que devo pensar em e como variáveis ​​aleatórias e que desejo comparar a distância entre e como variáveis ​​aleatórias. Tenho a intuição de que os circuitos estão sendo usados ​​como uma espécie de "teste" para ver se pode ser "descoberto". O que realmente estou lutando é por que a condição é a correta. Alguém tem algum conselho sobre como pensar nessa definição?xyxG(y)G()

user12484
fonte
Verifique a ortografia dos nomes dos autores ...
rphv
@rphv corrigiu.
Suresh Venkat

Respostas:

21

Existem dois aspectos que precisam ser mencionados.

A primeira é a idéia geral de definir um PRG, fazendo com que sua saída pareça diferente de uniforme para pequenos circuitos . Essa idéia remonta a Yao e é realmente a definição mais forte possível que você pode pedir ao apontar explicitamente a pseudo-aleatoriedade para observadores com limites computacionais .

O segundo aspecto é a escolha dos parâmetros em que limitamos o tamanho do circuito para e a diferença de probabilidade de aceitação em 1 / n , onde n também é o tamanho da saída PRG. Esta escolha é um pouco diferente do que a um cripto habitual onde o tamanho do circuito é p o l y ( n ) e a diferença de probabilidade é necessário para ser mais pequeno do que qualquer p o l y ( n ) . No nosso caso, parâmetros específicos (em vez de p o l y ( n )n1/nnpoly(n)poly(n)poly(n)) foram necessários para obter os melhores resultados, incluindo, em particular, simulações polinomiais. Embora, em princípio, pudéssemos ter três parâmetros diferentes, verificou-se que nossos resultados funcionavam essencialmente da mesma maneira, portanto os dobramos em um único (além do tamanho de entrada que foi visto como uma função de n )l(n)n

Noam
fonte
Obrigado Noam pela resposta. Foi muito útil.
user12484
4

Não sou especialista em nada disso, mas um componente-chave da definição de pseudo-aleatoriedade (em oposição a tentativas de definir aleatoriedade) é que o objetivo de algo "pseudo-aleatório" é enganar um circuito. Em outras palavras, a motivação é pensar na sequência pseudo-aleatória sendo fornecida ao circuito em vez da sequência verdadeiramente aleatória.

Nesse sentido, não é verdade que você esteja tentando fingir que e G ( y ) "parecem iguais". É que eles "parecem iguais" a um circuito (de complexidade necessariamente limitada).xG(y)

Portanto, o papel do circuito é crucial, ao invés de ser apenas uma "função de teste".

Suresh Venkat
fonte
2

Felizmente, posso expandir um pouco a resposta de Suresh. Primeiro, eu não acho que o rigor da desigualdade é necessária em sua , e eu também não sou certo porque 1 / n é necessário, e não 1 / 2 n ou outra coisa. No entanto, na prática, acho que 1 / n é suficiente para obter alguns resultados teóricos interessantes.()1 1/n1 1/2n

Mas então você quase certamente deseja afirmar que cada é computável em uma certa quantidade de tempo, digamos exponencial. Além disso, acho que você terá que afirmar que l ( n ) < n . Você pode pensar em l ( n ) como o comprimento da semente. Assim L i é pseudo-aleatória que se pode aumentar o número de bits de uma sequência aleatória de comprimento l ( n ) sem ser detectado por um circuito de tamanho inferior a n .GEueu(n)<neu(n)GEueu(n)n

Jonathan Gallagher
fonte