miniatura|386x386px|Visualització de la generació de nombres pseudoaleatoris a [0, 8] utilitzant un generador congruencial lineal. Les dues files superiors mostren un generador amb m = 9, a = 2 i c = 0 que genera nombres d'esquerra a dreta. Una llavor d'1 dóna una longitud de cicle de 6, però una llavor de 3 dóna una longitud de cicle de només 2. Si s'utilitzen a = 4 i c = 1 (fila inferior), s'obté una longitud de cicle completa de 9 amb qualsevol llavor. En informàtica teòrica i criptografia, un generador pseudoaleatori (PRG) per a una classe de proves estadístiques és un procediment determinista que assigna una llavor aleatòria a una cadena pseudoaleatòria més llarga de manera que cap prova estadística de la classe no pugui distingir entre la sortida del generador i la distribució uniforme. La llavor aleatòria en si mateixa és normalment una cadena binària curta extreta de la distribució uniforme.

A la literatura s'han considerat moltes classes diferents de proves estadístiques, entre elles la classe de tots els circuits booleans d'una mida determinada. No se sap si existeixen bons generadors pseudoaleatoris per a aquesta classe, però se sap que la seva existència és, en cert sentit, equivalent a les fites inferiors dels circuits (no provades) en la teoria de la complexitat computacional. Per tant, la construcció de generadors pseudoaleatoris per a la classe de circuits booleans d'una mida determinada es basa en supòsits de duresa actualment no provats.

Definició Deixa sigui una classe de funcions. Aquestes funcions són les proves estadístiques que el generador pseudoaleatori intentarà enganyar, i solen ser algorismes. De vegades, les proves estadístiques també s'anomenen adversaris o distintors. La notació en el codomini de les funcions és l'estrella de Kleene.

Una funció amb és un generador pseudoaleatori contra amb biaix si, per a cada en , la distància estadística entre les distribucions i és com a màxim , on és la distribució uniforme en .

La quantitat s'anomena longitud de la llavor i la quantitat s'anomena estirament del generador pseudoaleatori.

Un generador pseudoaleatori contra una família d'adversaris amb biaix és una família de generadors pseudoaleatoris , on és un generador pseudoaleatori contra amb biaix i la longitud de la llavor .

En la majoria d'aplicacions, la família representa algun model de computació o algun conjunt d'algorismes, i s'interessa a dissenyar un generador pseudoaleatori amb una longitud de llavor i un biaix petits, i de manera que la sortida del generador es pugui calcular amb el mateix tipus d'algorisme.

En criptografia En criptografia, la classe normalment consisteix en tots els circuits de mida polinòmica a l'entrada i amb un sol bit de sortida, i s'interessa a dissenyar generadors pseudoaleatoris que siguin computables mitjançant un algorisme de temps polinòmic i el biaix dels quals sigui insignificant en la mida del circuit. Aquests generadors pseudoaleatoris de vegades s'anomenen generadors pseudoaleatoris criptogràficament segurs (CSPRG).

No se sap si existeixen generadors pseudoaleatoris criptogràficament segurs. Demostrar que existeixen és difícil, ja que la seva existència implica P ≠ NP, cosa que es creu àmpliament però és un problema notòriament obert. L'existència de generadors pseudoaleatoris criptogràficament segurs és àmpliament acceptada. Això es deu al fet que s'ha demostrat que els generadors pseudoaleatoris es poden construir a partir de qualsevol funció unidireccional que es cregui que existeix. Els generadors pseudoaleatoris són necessaris per a moltes aplicacions en criptografia.

El teorema del generador pseudoaleatori demostra que els generadors pseudoaleatoris criptogràficament segurs existeixen si i només si existeixen funcions unidireccionals.

Usos Els generadors pseudoaleatoris tenen nombroses aplicacions en criptografia. Per exemple, els generadors pseudoaleatoris proporcionen un anàleg eficient dels paquets d'un sol ús . És ben sabut que per xifrar un missatge m de manera que el text xifrat no proporcioni cap informació sobre el text clar, la clau k utilitzada ha de ser aleatòria sobre cadenes de longitud |m|. El xifratge perfectament segur és molt costós pel que fa a la longitud de la clau. La longitud de la clau es pot reduir significativament mitjançant un generador pseudoaleatori si la seguretat perfecta se substitueix per la seguretat semàntica. Les construccions comunes de xifratges de flux es basen en generadors pseudoaleatoris.

Els generadors pseudoaleatoris també es poden utilitzar per construir criptosistemes de clau simètrica, on un gran nombre de missatges es poden xifrar de manera segura sota la mateixa clau. Aquesta construcció es pot basar en una família de funcions pseudoaleatòries, que generalitza la noció de generador pseudoaleatori.

A la dècada del 1980, les simulacions en física van començar a utilitzar generadors pseudoaleatoris per produir seqüències amb milers de milions d'elements, i a finals de la dècada del 1980, s'havien desenvolupat proves que alguns generadors comuns donaven resultats incorrectes en casos com ara les propietats de transició de fase del model d'Ising 3D i les formes dels agregats limitats per difusió. Després, a la dècada del 1990, diverses idealitzacions de simulacions físiques, basades en passejades aleatòries, funcions de correlació, localització d'estats propis, etc., es van utilitzar com a proves de generadors pseudoaleatoris.

Referències

Categoria:Nombres Categoria:Alectoris