Puncte:1

Securitate dovedibilă: reducere imposibilă atunci când mesajele sunt criptate/securitate semantică cu funcție în funcție de rezultatul adversarului

drapel us

Am o problemă cu un protocol pentru care pot dovedi securitatea dacă mesajele trimise de adversar sunt trimise clar, dar nu mai pot dovedi securitatea dacă mesajele trimise de adversar sunt criptate... și asta este puțin ciudat, deoarece mă aștept ca protocolul să fie sigur și în al doilea caz.

Mai exact, mă gândesc la un protocol pentru care un server Bob primește un mesaj $k$ de la Alice (aceasta poate fi văzută ca o criptare a unui șir de biți $d_0$ sub cheia publică secretă $t_k$) și trimite înapoi un mesaj $y$ (care poate fi văzută și ca o criptare a unor mesaje $x$ sub aceeași cheie publică $k$ lui Alice: nu că din cauza formei protocolului chiar trebuie să folosesc exact aceeași cheie). În dovada de securitate, aș dori să arăt că niciun Bob rău intenționat nu poate găsi o valoare secretă $\theta_\pi=f(x,d_0)$ ar trebui să arate aleatoriu altfel.

Vestea bună este că dacă știu $x$, pot inversa $f$ si gaseste $d_0$. Prin urmare, dacă un Bob rău intenționat știe $x$, aș putea face o reducere pentru a dovedi că dacă Bob poate găsi $\theta_\pi$ ei le știe și Bob $d_0 = f^{-1}(x,\theta_\pi)$: aceasta este o contradicție, deoarece criptarea este securizată IND-CPA.

Din păcate, această reducere nu funcționează, deoarece Bob rău intenționat poate să nu „știe” $x$: trimit doar o versiune criptată $y$ din ea: și în timpul reducerii nu pot decripta asta $y$ deoarece cheia este cunoscută doar de Alice (acest lucru este inevitabil în cazul meu)...

Există unele metode pentru a demonstra securitatea în acest caz? Cred Am nevoie de ceva asemănător cu securitatea semantică dar în cazul în care funcția care este calculată nu este eficient calculabilă (acest lucru este deja cazul în definiția actuală) și, de asemenea, depinde de unele rezultate ale adversarului.

EDITAȚI | ×

Pentru a-i răspunde lui Mikero, cred că în argumentația ta trebuie să spunem așa ceva:

introduceți descrierea imaginii aici

Dacă reușim să obținem cutia potrivită, atunci sunt de acord că dovada urmează ușor. Dar nu sunt sigur cum să demonstrez echivalența dintre aceste două scenarii. Nu cred că aceasta este o reducere directă a securității IND-CPA, deoarece distincția are și acces la $\theta_\pi$ care este legat de unele informații despre o decodare a $y$. Bănuiesc că ar fi bine să arătăm că prima diagramă este echivalentă cu

introduceți descrierea imaginii aici

dar nu sunt sigur cum să demonstrez asta (desigur $Funcție ideală_1$ se distinge de $Funcție ideală_3$, întrebarea este când adăugăm simulatorul deasupra).

drapel us
Se pare că Alice este sinceră în această situație, așa că simulatorul ar trebui să genereze cheia publică a lui Alice. Apoi, simulatorul ar putea decripta textele cifrate criptate sub acea cheie publică și ar putea face reducerea obișnuită. BTW, ce se întâmplă dacă Bob pur și simplu ecou înapoi aceeași criptare de $d_0$?
drapel cn
Alternativ, modalitatea standard de a se asigura că adversarul cunoaște textul simplu ar fi adăugarea unei dovezi de cunoaștere textului cifrat.
Léo Colisson avatar
drapel us
@Maeher Mulțumesc pentru răspuns.Din păcate, acest lucru nu poate funcționa în cazul meu, deoarece sunt într-un cadru cuantic: practic, pentru ca adversarul să învețe $x$, trebuie să-și distrugă starea (și apoi, protocolul nu mai este util). Desigur, aș putea face o abordare „taie și alege” cerând din când în când să distrug statul și din când în când să continui, dar apoi obțin doar securitate polinomială :-( De asemenea, nu cred că abordarea propusă de Mikero funcționează, voi încerca să elaborez într-un alt mesaj.
Léo Colisson avatar
drapel us
@Mikero Mulțumesc pentru răspuns, dar nu sunt sigur dacă funcționează (cel puțin în cazul meu). Dacă simulatorul alege cheia publică a lui Alice, avem nevoie de un argument pentru a spune că simulatorul poate cripta un $d_0'$ aleatoriu în loc de $d_0$ (pentru că $d_0$ nu ar trebui să se scurgă în simulator) fără a fi detectat. Cu toate acestea, nu cred că acest lucru este direct implicat de IND-CPA (vezi editarea mea). Am pierdut ceva?
Léo Colisson avatar
drapel us
@Mikero, de asemenea, dacă Bob ecou înapoi $y$, atunci ar seta practic $x = 00$ (ceea ce este perfect).
drapel cn
Nu sunt sigur că înțeleg cum este o problemă setarea cuantică. Vrei să spui că y este de fapt *nu* un text cifrat, ci o suprapunere arbitrară a textelor cifrate? În primul rând, de ce ai permite adversarului să facă asta? Și în al doilea rând, din câte văd, puteți calcula la fel de bine dovada cunoștințelor pe acea suprapunere.
Léo Colisson avatar
drapel us
@Maeher Pentru că scopul protocolului este de a crea o stare cuantică necunoscută lui Bob. Practic, pentru a obține $y$, Bob ar trebui să creeze o suprapunere $\sum_x | x \rangle | g(x) \rangle$. Funcția $g$ este 2-la-1: deci după măsurarea celui de-al doilea registru obținem $| x \rangle+|x' \rangle$ pe primul registru pentru cele 2 preimagini de $g$. Din această stare putem obține o nouă stare cuantică care va fi folosită în alte protocoale (adversarul nu poate descrie pe deplin această stare deoarece nu poate inversa $g$). Dacă Bob ar fi vrut să învețe un $x$, l-ar putea măsura... dar l-ar distruge.
Léo Colisson avatar
drapel us
Deci $y$ este un text cifru clasic, dar este determinat folosind o suprapunere care este încă utilă după încheierea protocolului.

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.