Puncte:3

Criptografia bazată pe zăbrele: secret din distribuția gaussiană chi

drapel pl

Într-o prelegere, de Chris Peikert (link 40:20), el a arătat criptosisteme mai eficiente, care au secretul să fie extras din distribuția erorilor gaussiene $\chi$. În prelegere, el a spus „unele aplicații care chiar au nevoie de secrete pentru a veni din distribuția erorilor și nu funcționează chiar atât de bine dacă provin din distribuția uniformă” și adaugă „dintr-un motiv ciudat, aceasta este forma care primește mai departe în ceea ce privește construirea de aplicații precum Full Homomorphic Encryption (FHE)".

  1. Știm astăzi de ce este așa?
  2. Ce eficiență aduce distribuția erorilor peste una uniformă?

Editare: actualizați informațiile

Hilder Vitor Lima Pereira avatar
drapel us
Ești sigur că a spus că aplicația a funcționat doar cu secret gaussian sau cerința este ca secretul să aibă o normă mică? Poate ar trebui să verificați acest lucru, pentru că unele scheme FHE funcționează bine când secretul este scurt, dar „scurt” poate fi gaussian, binar, ternar...
Karim avatar
drapel pl
Îmi pare rău pentru răspunsul târziu, am încercat să aflu unde am auzit asta. Deci nu a fost de la Vadim Lyubashevsky, ci de la Chris Peikert în timpul unei școli de iarnă. Voi actualiza prin întrebare cu link către prelegere.
Puncte:2
drapel in

Unele operațiuni FHE, cum ar fi „schimbarea/reducerea modulului”, au nevoie de un „mic” secret LWE pentru a funcționa. În mod similar, unele criptosisteme precum Lyubashevsky-Peikert-Regevâ10 și Lindner-Peikertâ11 au chei și/sau texte cifrate mai mici (și, în mod corespunzător, operațiuni mai rapide) datorită utilizării unui „secret” mic.

Secretele mai mici oferă o eficiență mai bună în aceste sisteme, dar pentru securitate există o limită la cât de mici le putem considera. Sa dovedit în Applebaum-Cash-Peikert-Sahaiâ09 că extragerea secretului LWE din distribuția erorilor (care dă un secret relativ mic) nu este în esență mai puțin sigură decât utilizarea unui secret uniform aleatoriu.

Karim avatar
drapel pl
Deci, dacă am înțeles bine, extragerea secretului din distribuția erorilor ucide 2 păsări dintr-o singură piatră. Oferă mici secrete fără a sacrifica securitatea făcând secretul prea mic. Este corect?
Chris Peikert avatar
drapel in
Da, asta este versiunea scurtă.
Hilder Vitor Lima Pereira avatar
drapel us
[LWE cu secrete binare este, de asemenea, dovedit a fi sigur](https://theoryofcomputing.org/articles/v014a013/v014a013.pdf), trebuie doar să măriți dimensiunea $n$. Cu toate acestea, cred că nu există o reducere de la cel mai rău caz la mediu pentru RLWE cu secrete binare sau ternare, dar oamenii îl folosesc oricum, ca în HElib sau TFHE, deoarece este încă posibil să se estimeze securitatea concretă pentru astfel de secrete și sunt chiar mai scurte decât atunci când distribuția este gaussiană...
Chris Peikert avatar
drapel in
@HilderVitorLimaPereira Tot ce este adevărat. Cu toate acestea, utilizarea unui secret binar/ternar se află pe un teren mai puțin ferm (din punct de vedere al securității) decât utilizarea distribuției de erori, deoarece se bazează doar pe criptoanaliza cunoscută, în timp ce utilizarea distribuției de erori are o dovadă de duritate strânsă bazată pe problema LWE inițială. Deci avem un compromis tipic între ceea ce pare a fi sigur și ceea ce putem dovedi.

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.