Este această construcție un OWF?

Sugestie: Fie $G'$ un PRG. Atunci $G$ definit ca $G(x_1\|x_2) = G(x_1)||x_2$ pentru suficient timp $x_1$ este, de asemenea, un PRG.

@Maeher suficient de mult =?

@kelalaka Orice fracție constantă va funcționa. Să spunem 1/2 din lungimea de intrare pentru o construcție din beton.

@Maeher ar trebui să construiesc un contraexemplu cu sugestia ta?

Asta ar putea funcționa.

@Maeher cred că pe baza sugestiei dvs. putem construi funcția $f^*(x_1||x_2) = f(G'(x_1)||x_2 \oplus (0^{\lambda}||x1||x2) ))$ și dacă avem $|G'(x_1)| = \lambda + |x1|$ avem, de asemenea, că a doua parte a intrării lui $f$ este întotdeauna zero (din cauza xor). Prin urmare, probabilitatea de a găsi o pre-imagine de $f^*$ este limitată față de alegerea $x_1$ în acest caz. Dar avem nevoie de un $x_1$ suficient de mare pentru a avea un PRG... Având în vedere $|x_1|=\lambda/2$ ca în exemplul dvs., avem totuși o probabilitate de a găsi o pre-imagine de $2^{-\lambda /2}$ care ar trebui să fie încă neglijabil.

Esti sigur de parametri? face $f^*$ de la $2\lambda$ sau $\lambda$ de la $G$ de la $\lambda$. De asemenea, @Maeher a vrut să scrie $G(x_1\|x_2) = G'(x_1)||x_2$, adică o construcție pentru un exemplu patetic $PRG$ la ....

@kelalaka $f*$ ia o intrare de lungime $\lambda$, care poate fi $x_1||x_2$. Dar nu înțeleg unde ar putea fi contraexemplul, având în vedere că $G(x_1||x_2) = G'(x_1)||x_2 este sigur pentru $x_1$ suficient de mare.

Sfat 2: Un OWF este garantat a fi greu de inversat doar dacă intrările sunt eșantionate conform distribuției uniforme. O distribuție care conține doar intrări care se termină cu multe zerouri este foarte departe (și ușor de distins de) uniformă.

Așa că m-am gândit să construiesc un OWF "prost" $f'(x) $ care, în cazul în care ultimii $\lambda$ biți ai intrării sale sunt nuli, iese intrarea în sine sau, în caz contrar, ieșirea normală de $f$. Funcția ar trebui să fie în continuare OWF, deoarece probabilitatea de a avea o intrare aleatorie care se termină cu $0^{\lambda}$ este $2^{-\lambda}$ și, prin urmare, neglijabilă. Dar chiar dacă atacatorul vede $G'(x)\oplus(0^{\lambda}||x)$, ce poate face cu el? Cum poate deduce $x$? (Apropo, mulțumesc mult pentru ajutor!)

Există și alte moduri prin care un OWF se comportă prost. Amintiți-vă, nu trebuie să găsiți $x$. Trebuie doar să găsiți *o* preimagine, nu *aceeași* preimagine.

Cred că am înțeles! Construiesc un OWF $f'$ care returnează $1^{2\lambda}$ dacă ultimii ${\lambda/2}$ biți ai intrării sunt $0$ și ieșirea unui OWF normal $f$ în caz contrar. $f'$ este un OWF deoarece probabilitatea de a avea o intrare aleatorie care se termină cu $0^{\lambda/2}$ este $2^{-\lambda/2}$, dar construcția $f*$ poate fi ruptă ușor deoarece atacatorul va primi întotdeauna $1^{2\lambda}$ și, prin urmare, trebuie să trimită doar o preimagine care se termină cu $0^{\lambda/2}$ biți pentru a câștiga jocul. Este corect?

Contraexemplul tău ar trebui să funcționeze. Este o bună practică să scrieți dovezile că $f$ și $G$ pe care le construiți sunt de fapt un OWF și, respectiv, un PRG securizat. Atacul tău funcționează, dar este mai specific decât este necesar. $f^*(x_1\|x_2) = f(G(x_1\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\|x_2)\oplus( 0^\lambda\|x_1\|x_2) = f((G'(x_1)\oplus 0^\lambda\|x_1) \|0^{\lambda/2}) = 1^{2\lambda}$ deci $f^*$ este o funcție *constant* și *orice* valoare $2\lambda$ este o preimagine validă.

întrebarea această in alte limbi: