Puncte:1

Ce este exact un joc, un contestator și un adversar?

drapel cn

Iată înțelegerea mea despre conceptul de jocuri de securitate. Am îndrăznit câteva părți despre care nu sunt sigur.

Un obiect criptografic este definit formal de algoritmii săi și de noțiunile de securitate pe care le realizează.Astfel de noțiuni captează puterea unui adversar și arată cum adversarul poate „spărge criptosistemul”. „Defectarea unui criptosistem” înseamnă câștigarea unui JOC asociat cu securitatea criptosistemului. Jocul (adică algoritm) se joacă între un adversar și un contestator. Atât adversarul, cât și contestatorul sunt calculatoare care rulează algoritmi probabilistici. Probabilitatea ca adversarul să câștige ar trebui să fie neglijabilă în raport cu o probabilitate țintă pentru ca schema să fie sigură.

De exemplu, într-o schemă de criptare, un adversar puternic nu ar trebui să poată distinge criptări unul de celălalt chiar dacă acestea alege mesajele. Cu alte cuvinte, un adversar ghicește care a mușcat adversarul întors. Probabilitatea țintă este $\frac{1}{2}$, deoarece un adversar poate ghici aleatoriu ce bit a fost inversat. Adversarul trebuie să câștige cu probabilitate nu mai mult de $\frac{1}{2} +negl(n)$, Unde $n$ este parametrul de securitate din schemă.

  1. Un joc nu este un algoritm? Dacă nu, atunci ce este? https://www.shop.net/papers/games.pdf Shoup spune că sunt procese probabilistice. Dar există o diferență între procesele probabilistice și algoritmii probabilistici?
  2. Adversarii și contestatorii sunt computere? Ei fac niște calcule (chiar dacă procesul este ca un oracol aleatoriu). Este corect să spui așa?
  3. Ce este $n$ ar trebui să fie un parametru al?
Puncte:2
drapel us

Cu riscul de a fi pedant și pretențios (ați pus o întrebare despre terminologie până la urmă), vă propun să numiți aceste obiecte „programe interactive” mai degrabă decât algoritmi sau computere.

Este un joc nu un algoritm

Provocatorul și adversarul pot fi cu siguranță descriși în termeni de o anumită logică programatică/algoritmică. Dar cred că un algoritm este un non-interactiv lucru care ia o intrare, dă o ieșire și apoi este gata. Un joc de securitate criptografică este mai interactiv decât atât. Există adesea mai multe runde distincte în care se fac schimb de informații, iar contestatorul oferă de obicei o colecție de subrutine/oracole pe care adversarul le poate apela de multe ori. Cred că este important să evidențiem această natură interactivă.

Din punct de vedere tehnic, puteți identifica un program interactiv cu „funcția de acțiune următoare”, care este într-adevăr un algoritm simplu non-interactiv. De exemplu, provocatorul este caracterizat de un algoritm care calculează logica: „dacă adversarul face un fel de interogare, atunci răspunde cu acțiune”. De fapt, așa ar putea fi modul în care ați alege defini ce este un program interactiv, din punct de vedere al algoritmilor non-interactivi. În afară de astfel de definiții foarte formale, este rar să ne gândim și să vorbim cu adevărat despre contestatori și adversari în acest fel, dar ocazional este util să ne gândim la specificațiile protocolului în acest fel.

Sunt computere adversarii si contestatorii

Cred că un computer este un dispozitiv care poate face ceea ce îi spune un program să facă. Adversarii și contestatorii sunt computere care rulează specific programe -- provocatorul pentru un anumit joc de securitate rulează un program fix, dar considerăm un adversar care rulează un program arbitrar.

Ce este $n$ ar trebui să fie un parametru al?

A fi un parametru înseamnă: este o valoare care este aleasă extern și este oferită public atât contestatorului, cât și adversarului. Parametrul de securitate este dat ca intrare pentru toți algoritmii din schema criptografică (deși această intrare nu este adesea scrisă în mod explicit). De obicei, parametrul de securitate specifică dimensiunea cheilor etc.

Parametrul de securitate este ca un buton pe care îl puteți roti. O valoare mai mare face ca rularea algoritmilor criptografici să fie puțin mai costisitoare, dar mult mai costisitoare să o rupă. Rotiți butonul până când vă simțiți confortabil cu cât de greu este să rupeți schema și aceasta este valoarea pe care o utilizați când rulați această schemă.

eternalmothra avatar
drapel cn
Acest lucru este foarte util! Am vrut să fiu pedant (ei bine, pedagogic) aici. Singurul lucru de care nu sunt sigur: $n$ este de fapt un parametru de securitate sau este dimensiunea intrării? Distincția ar putea fi că aveți nevoie de chei de lungime X pentru a obține Y biți de securitate, de exemplu.

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.