Puncte:2

Barak și colab. dovada că ofuscarea cutiei negre este imposibilă

drapel br

Am încercat să analizez dovada clasică prezentată de Barak și colab. care susține că Black-Box Obfuscation nu este posibilă pentru (ceea ce pare a fi) majoritatea claselor de programe.

Dovada este prezentată în așa fel în care se spune că dacă există un program criptat C'(a, b, x) care revine b dacă și numai dacă a = x, și un alt program criptat D'(a, b, f) care revine 1 dacă un numai dacă f(a, b, x) = b, atunci D'(a, b, C(a, b, x)) = 1 cu o probabilitate de 1. Acest lucru va însemna, de asemenea, că un atacator va putea diferenția C'(a, b, x) dintr-o altă funcție Z() care revine 0 în toate punctele, ca D'(a, b, Z()) = 1 cu o probabilitate mai mică decât 1.

Totuși, dovada nu are sens pentru mine, deoarece presupunând că un atacator nu poate testa fiecare valoare a lui A și b s-ar părea că nu există nicio modalitate de a concluziona că există vreo diferență între C'(a, b, x) și Z(). Black-Box Obfuscation ar fi valabil, totuși, dacă singura modalitate de a diferenția două programe ar fi testarea fiecărei intrări și inspectarea ieșirii.

Există cineva care ar putea ajuta să-mi explice cum această dovadă este cu adevărat concludentă pentru a spune că Black-Box Obfuscation (în cea mai mare parte) nu este posibilă?

kodlu avatar
drapel sa
vă rugăm să furnizați un link către lucrare, dacă este disponibil online
James avatar
drapel br
@kodlu Am inclus acum linkul către demonstrația menționată (lucrarea o descrie într-o manieră mult mai matematică decât am făcut-o eu, dar deoarece este o demonstrație destul de faimoasă, am dobândit o formă simplificată pentru a o prezenta aici).
Puncte:3
drapel us

Lucrarea definește două clase de funcții:

\begin{align*} C_{\alpha,\beta}(x) &= \begin{cases} \beta & \mbox{ if } x=\alpha \ 0^k & \mbox{ otherwise} \end{cases} \ D_{\alpha,\beta}(F) &= \begin{cases} 1 & \mbox{ if } F(\alpha)=\beta \ 0 & \mbox{ otherwsie} \end{cases} \end{align*}

Ideea este că dacă vi se oferă orice circuit $C^*$ (chiar și unul obfuscat) calculând aceeași funcție ca $C_{\alpha,\beta}$ atunci $D_{\alpha,\beta}(C^*)=1$.

Pe de altă parte, dacă aveți doar acces la cutia neagră $C_{\alpha,\beta}$, și $\alpha,\beta$ sunt alese uniform, atunci va fi greu să veniți cu o intrare care cauzează $D_{\alpha,\beta}$ la ieșirea 1.

Intuitiv, având acces la o ofuscare a $C_{a,b}$ vă oferă strict mai multă putere decât accesul la cutia neagră $C_{a,b}$.

Totuși, dovada nu are sens pentru mine, deoarece presupunând că un atacator nu poate testa fiecare valoare a lui $\alpha$ și $\beta$ nu pare să existe nicio modalitate de a concluziona că există vreo diferență între $C_{\alpha,\beta}$ și $Z$ (o funcție care scoate zero pe toate intrările).

Atacatorul nu distinge ofuscările de $C_{\alpha,\beta}$ din ofuscarile de $Z$ încercând fiecare intrare. Atacatorul distinge prin trecerea ofuscarii ca intrare la $D_{\alpha,\beta}$. $D_{\alpha,\beta}$ are "corectul" $\alpha,\beta$ copt în ea -- știe unde să caute, astfel încât să poată distinge cu ușurință $C_{\alpha,\beta}$ din $Z$.

James avatar
drapel br
Dar cum poate un hacker să știe că `a` și `b` sunt incluse în ambele funcții ofucate (și, prin urmare, că `D'(C')` va returna întotdeauna `1`), cu excepția cazului în care se întâmplă să fie acel `a` a fost copt pentru a fi egal cu `x`? Cu excepția acestui caz, „C” se pare că ar părea în continuare identic cu „Z”? De asemenea, această dovadă nu ar sugera pur și simplu că Black-Box Obfuscation este imposibilă în scenariul foarte specific în care un hacker găsește, de exemplu, două funcții care au exact variabilele corecte?
drapel us
Când definim securitatea pentru criptare, spunem (de exemplu) că textele cifrate par imposibil de distins de aleatorii, chiar dacă adversarul trebuie să aleagă textul simplu. Când definim securitatea VBB pentru ofuscare, spunem că programul ofuscat nu scurge mai mult decât accesul cutie neagră la funcție, chiar dacă adversarul trebuie să aleagă funcția. De asemenea, mai târziu în Barak et al. dovadă că combină atât C, cât și D într-un singur program, ceea ce asigură că C și D au în minte aceleași $\alpha$ și $\beta$.
James avatar
drapel br
Chiar dacă un adversar a ales `a` și `b` atât pentru `C`, cât și pentru `D`, dacă le-am da înapoi atât `Z'` cât și `C'` la o dată ulterioară, nu ar putea spune care este care? Asta cu excepția cazului în care au copt și în `x`. Dacă au inclus fiecare variabilă, atunci dovada pare puțin redundantă, deoarece creează în mod deliberat o funcție „C” care returnează întotdeauna „1” și o funcție „Z” care returnează întotdeauna „0”. Dacă `x` nu este inclus, atunci adversarul trebuie să testeze fiecare `x` atât pe `C'` cât și pe `Z'` până când produc rezultate diferite?
Manish Adhikari avatar
drapel us
Dacă doriți un răspuns mai intuitiv care implică o scurgere evidentă de informații, luați în considerare pentru un moment că programul $C^*_{\alpha,\beta} (.)$ care calculează aceeași funcție ca $C_{\alpha,\beta} ( .)$ cu $\alpha$ și $\beta$ alese aleatoriu dintr-un spațiu mare. Acum schimbați ușor $D_{\alpha,\beta} (F)$ astfel încât să returneze $\beta$ dacă $F(\alpha)=\beta$ și $0^k$ în caz contrar. Având acces la $D$, puteți extrage $\beta$ dintr-o cutie neagră care rulează $C$. Dar de la $C^*$?
James avatar
drapel br
Probabil va trebui să-mi cer scuze pentru că s-ar putea să-mi lipsească încă ceva aici. Totuși, aș spune @ManishAdhikari că mi-aș imagina că veți extrage exact la fel de multe informații despre $\beta$ dintr-o cutie neagră care rulează $C$ ca și din $C*$, cu excepția cazului în care știți deja în ce se coace $\alpha$ , sau puteți coace în $\alpha$, $\beta$ și $x$ astfel încât $C_{\alpha,\beta}(x)$ va returna întotdeauna $\beta$ și niciodată $0^k$ . În toate celelalte cazuri, ar trebui să testați fiecare $x$ până când găsiți valoarea pe care funcția o returnează $\beta$?
Manish Adhikari avatar
drapel us
Da, se pare că încă ratezi ideea. Am spus că $D$ este disponibil pentru tine. Cu $C^*$, indiferent cât de obscurcate ar fi $\alpha$ și $\beta$ în ​​program, puteți extrage $\beta$ pur și simplu alimentându-l la $D$. Dar o cutie neagră care rulează $C$ nu poate fi dată la nimic și ești blocat să-i dai doar intrare și să vezi rezultatul. Extragerea $\beta$ în ​​acest caz va necesita să încercați o mulțime de $x$, așa cum ați spus pe bună dreptate.

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.