Puncte:4

Obfuscare care nu se poate distinge de criptare funcțională

drapel br

Care este diferența dintre criptarea funcțională și obfuscarea indistinguită? Are unul dintre ei o securitate mai puternică decât celălalt?

Puncte:4
drapel ag

Acestea sunt primitive echivalente presupunând existenţa funcţiilor unidirecţionale, ceea ce presupune $\mathbf{P}\neq\mathbf{NP}$$^*$. S-a arătat în [G+,SW] că IO plus OWF-uri implică FE cu cheie publică.$^{**}$ Reversul, că FE cu cheie publică sub-exponențial-securizată (cu o anumită proprietate de succintitate) implică IO, a fost arătat în [BV].

Pe de altă parte, așa cum s-a subliniat în comentariul lui @integrator, dacă $\mathbf{P}=\mathbf{NP}$ atunci există IO (pur și simplu alegeți cel mai mic/primul circuit din punct de vedere lexicografic care calculează aceeași funcție), dar FE (care implică PKE) nu există.

$^*$Acest lucru a fost relaxat $\mathbf{NP}\not\subseteq \mathbf{io}- \mathbf{BPP}$ în [K+].

$^{**}$[G+] presupune PKE și NIZK în plus față de IO. Acestea s-au dovedit ulterior a fi implicate de IO și OWF-uri [SW].

[BV] Bitansky și Vaikuntanathan, Indistinguirea Obfuscare de criptarea funcțională, FOCS'15

[G+] Garg și colab., Obscurcarea de indistinguire a candidatului și criptarea funcțională pentru toate circuitele, FOCS'13.

[K+] Komargodski et al, Funcții unidirecționale și ofuscare (im)perfectă, FOCS'14

[SW] Sahai și ape, Cum să utilizați Obfuscarea indistinguirii: criptare refuzată și multe altele, STOC'14

integrator avatar
drapel cn
Este puțin o scurtătură să spunem că sunt echivalente, deoarece alte primitive precum NIZK-uri sau PKE sunt folosite în ambele direcții. Și, de fapt, dacă P=NP, atunci există iO pentru toate circuitele, dar criptarea funcțională nu există.
Hilder Vitor Lima Pereira avatar
drapel us
[BV] spune că „criptarea funcțională cu cheie publică cu circuite de criptare succinte și securitate subexponențială” implică iO. Mă întreb dacă construcțiile FE standard/existente sunt subexponențiale sigure și succinte...
ckamath avatar
drapel ag
@integrator: E adevărat. Dar ori de câte ori se vorbește despre IO, se presupune implicit OWF-uri, ceea ce implică $\mathbf{P}\neq\mathbf{NP}$, (deoarece IO în sine nu este foarte util.). Și IO+OWF implică PKE/NIZK (Sahai and Waters, STOC'14). Vom modifica răspunsul pentru a face acest lucru mai explicit.
ckamath avatar
drapel ag
@HilderVitorLimaPereira: Un punct bun. Va arunca o altă privire la [BV].

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.