- Generator bit pseudo-aleator (GBPSA)
- Este un algoritm determinist care porneste de la o secventa binara aleatoare de lungime k, numita cheie de generare, si produce o secventa binara de lungime l>>k, numita secventa de biti pseudo-aleatori
Un GBPSA este un program determinist de timp polinomial G:{0, 1}k → {0, 1}l care satisface:
- l > k
- distributia de probabilitate Gl se obtine din distributia normala Uk astfel: y=G(x), y ∈ Gl, x ∈ Uk
- Teste in timp polinomial
- Un generator bit pseudo-aleator trece toate testele statistice in timp polinomal daca un algoritm de timp polinomial nu poate face distinctia intre o secventa de la iesirea generatorului de bit pseudo-aleator si o secventa aleatoare de bit cu o probabilitate semnificativ mai mare ca 1/2
Fie Xn si Yn doua distributii de probabilitate pe {0, 1}n. {Xn} este indistinctibila in timp polinomial de {Yn} daca ∀ MTP, A, ∀ polinom Q, ∃ n>n0 ai | Prt∈Xn (A(t)=1) - Prt∈Yn (A(t)=1) | < 1/Q(n)
Pentru distributia uniforma de probabilitate Un, ∀ a ∈ {0, 1}n, Prx∈Un [x=a] = 1/ 2n
- Testul bitului urmator
- Un generator bit pseudo-aleator trece testul bitului urmator daca nu exista un algoritm de timp polinomial care sa poata prezice bitul "l+1" cu o probabilitate semnificativ mai mare ca 1/2, in baza primilor "l" biti ai unei secventa de la iesirea generatorului de bit pseudo-aleator
Un generator de bit pseudo-laeator trece testul bitului urmator ⇔ generatorul de bit pseudo-aleator trece testele de timp polinomial
- Generator sigur criptografic de bit pseudo-aleator
- Este un GBPSA care trece testul bitului urmator, posibil in niste ipoteze matematice plauzibile, dar nedemonstrate
# posted by Sorin Badescu @ 2:13 PM
