Puncte:0

Demonstrați că o funcție G nu este un generator pseudoaleator

drapel de

O funcție G(x) = x || x (unde â||â denotă concatenarea șirurilor). Se dă că G nu este generatorul pseudo-aleatoriu. Poate cineva să descrie cum putem demonstra acest lucru. Devin puțin confuz în conceptul de generator pseudo-aleatoriu.

Ce am înțeles până acum - Definiția formală a generatorului pseudo-aleatoriu este dată ca $\Pr[PRG_{A,G(n)} = 1] ⤠1/2 + negl(n)$. Aici putem observa că pentru această funcție G ieșirea va avea prima și a doua jumătate egale. Cum să folosiți acest lucru cu definiția formală pentru a demonstra că G este nesigur?

Maarten Bodewes avatar
drapel in
După cum se spune, este încă o sarcină fără indicații clare de efort. Vă rugăm să [editați] întrebarea pentru a include raționamentul dvs.; nu trebuie să fie corect, trebuie doar să fie *acolo*.
Marc Ilunga avatar
drapel tr
Bun venit la Crypto.SE! O abordare utilă aici ar fi să scrieți definiția unui PRG și garanțiile de securitate ale unui astfel de obiect. De acolo, poate puteți vedea de ce această instanță anume nu funcționează? Acest lucru poate ajuta și la editarea comentariului într-un mod conform (vezi primul comentariu)
archie09 avatar
drapel de
Multumesc ca m-ai anuntat. Am editat intrebarea. Chiar aș aprecia ajutor cu conceptul.
fgrieu avatar
drapel ng
@archie09: ați sărit multe din definiția formală a PRG.Ca și domeniile de intrare și de ieșire, poate este o proprietate de expansiune (unele surse omit peste asta) și cu siguranță contextul formulei: ceva pe tonul „pentru orice algoritm probabilistic polinomial-timp $\mathcal A$, există o valoare neglijabilă. funcția $\mathrm{negl}$ astfel încât..." Ca o parte relativ minoră, nu recunosc formula ca fiind cea din definiția unui PRG pe care l-am studiat, dar s-ar putea să fi folosit o altă referință.
archie09 avatar
drapel de
@fgrieu Ați putea să-mi spuneți o sursă bună pe care o pot consulta pentru această definiție. Am încercat să caut, dar nu am reușit să înțeleg corect acest concept.
Maarten Bodewes avatar
drapel in
În cele din urmă, ar trebui să puteți demonstra cumva că un bit din ieșire nu are o șansă de 0,5 + $e$ să fie 0 sau 1, incluzând în același timp ieșirea anterioară. Ar trebui să fie ușor, nu? Cu toate acestea, nu văd cum să fac asta având în vedere doar probabilitatea din definiție, așa că vă las să faceți asta în mod formal.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.