Puncte:0

XOR din toți biții de $f(x)$ un bit hard-core

drapel cn

De ce să ia în considerare o întâmplare $r$ în construirea unui predicat hardcore în teorema Goldreich Levin? De ce să nu luați în considerare doar XOR-ul tuturor biților de intrare?

drapel cn
Fie $f : \{0,1\}^n \to \{0,1\}^n$ o funcție unidirecțională. Luați în considerare funcția $g : \{0,1\}^n \to \{0,1\}^{n+1}$ definită ca $g(x) = g(x_1\ldots x_n) := f( x)\Vert \bigoplus_{i=1}^{n} x_i$. $g$ este unică? Este xorul tuturor biților de intrare un predicat hardcore pentru $g$?
Zoey avatar
drapel cn
nu este, deoarece face parte din ieșire. Dar atunci de ce nu se poate face același lucru . Dacă includeți asta în ieșire, nu va fi prea hard-core, nu? De asemenea, XOR nu este cazul special când r este toate 1-urile?
drapel cn
Amintiți-vă că GL definește un OWF *specific*, pentru care produsul interior este hard-core.
drapel cn
$r$ face parte din *input* pe care nu o puteți *seta* la nimic, este aleasă uniform la întâmplare. Dar, în mod esențial, nu face parte din intrarea funcției *subiacente*, astfel încât acea funcție nu poate face nimic amuzant.
Zoey avatar
drapel cn
Permiteți-mi să încerc să înțeleg aici: XOR de biți nu este un bit hardcore pentru orice OWF, deoarece putem construi unul în care XOR face parte din ieșire. XOR poate fi un nucleu al funcției de bază $f$, se întâmplă dacă $r= 11...1$ (toți cei 1) este o alegere aleasă aleatoriu pentru intrarea transformării GL a $f$, adică $g$ .

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.