înregistrare Logare
Puncte:2
Titanlord avatar Crypto

Întrebare despre stilurile de dovezi de reducere

drapel tl
Titanlord

În criptografie, dovezile de securitate folosesc în principal tehnica de reducere. Acum am citit o mulțime de dovezi de reduceri și am făcut unele pe cont propriu și cred că le înțeleg destul de bine. Citind acele dovezi, am observat două stiluri principale ale unei astfel de reduceri.

Să zicem că avem o schemă $B$ bazat pe $A$. Noi stim $A$ este sigur. Dacă cineva dorește să dovedească securitatea $B$ prin reducerea lui la securitatea de $A$ el poate proceda astfel:

  1. Stil: Asumați-vă un adversar care se poate sparge $B$ $\Săgeată la dreapta$ Pentru reducerea se poate construi un nou adversar de rupere $A$ folosind ruperea adversarului $B$ $\Săgeată la dreapta$ Rezultatul este o contradicție care arată că nu există un adversar deloc neglijabil împotriva $B$
  2. Stil: Să presupunem un adversar ppt arbitrar împotriva $B$ $\Săgeată la dreapta$ Arătați (de exemplu, cu analiza stocastică a experimentului) că ruperea $B$ este la fel de greu ca ruperea $A$, prin urmare reduceți complexitatea ruperii $B$ la complexitatea ruperii $A$ $\Săgeată la dreapta$ Pentru că sunt doar adversari neglijabili împotriva $A$ nu există un adversar deloc neglijabil împotriva $B$

Desigur, acest lucru este simplificat, dar am vrut să vă fac o idee despre ceea ce am observat.

Intrebarile mele: Există într-adevăr aceste stiluri? Pot amândoi (scrise corect formal) să demonstreze la fel? Sunt ambele (în special stilul 1.) complete? Pentru ce dovezi ar trebui să folosim ce stil?

Editați | ×: O definiție mai precisă a stilului 2.: În Introducere în criptografia modernă, dovediți un criptosistem pe un PRG: În analiza stocastică, ei afirmă că ruperea criptosistemului este la fel de probabilă ca ruperea PRG.Ei folosesc acest lucru pentru a sugera că orice adversar arbitrar trebuie să fie neglijabil în mod: deoarece acest lucru este neglijabil și au aceeași probabilitate, celălalt trebuie să fie și el neglijabil.

(Notă: pe scurt, aș descrie 1. ca: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ și 2. ca: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)

125
0 + 0
drapel us
Mikero
În #2: „Arătați că ruperea lui B este la fel de grea ca ruperea lui A”, cu ce este diferită de numărul 1? Cum arăți acest lucru, în afară de utilizarea unui adversar B de succes pentru a construi un adversar A de succes? Ce vrei să spui mai exact prin „analiza stocastică a experimentului”? Aveți în minte un exemplu despre ceea ce înțelegeți prin numărul 2?
0
Răspunde
Titanlord avatar
drapel tl
Titanlord
Cred că [Manualul lui Katz & Lindell (ediția a 2-a)](https://www.cs.umd.edu/~jkatz/imc.html)) folosește stilul 2, de ex. pentru a demonstra criptoschema PRG pe care au construit-o.
0
Răspunde
drapel cn
Maeher
@Mikero Este diferit prin faptul că eviți în mod inutil și confuz să folosești un argument prin contradicție. Stilul 1 face afirmația „*A* și *nu B* implică o contradicție” din aceasta, apoi trageți concluzia că *B*, deoarece presupuneți *A*. Stilul 2. pe de altă parte face direct afirmația „*A* implică *B*” evitând ocolul inutil. Rezultatul final este același, cu excepția cazului în care aveți niște opinii ciudate despre logică.
0
Răspunde
drapel us
Mikero
@Maeher, interesant.Nu cred că stilul #1 implică neapărat o dovadă prin contradicție. O interpretez ca „dacă A este rupt, atunci B este rupt și el”. Contrapozitivul este că dacă B este sigur, atunci A este sigur. Există și alte stiluri de dovezi (pe care le prefer de fapt) care evită să comute înainte și înapoi între interpretările contrapozitive și rămân în întregime în lumea „dacă B este sigur decât A este sigur”, dar nu am recunoscut numărul 2 în acest articol. întrebare ca descriere a acelui stil.
0
Răspunde
kelalaka avatar
drapel in
kelalaka
Este de fapt că uneori $p \implies q$ nu este atât de evident de arătat, iar contrapozitivul poate fi mai ușor de arătat. De aceea le alegem. CS are câteva întrebări despre reduceri de la care provine termenul [1](https://cs.stackexchange.com/q/11209/94479) și chiar au o etichetă [reduceri](https://cs.stackexchange.com /questions/tagged/reductions?tab=Voturi)
0
Răspunde
drapel cn
Maeher
@Mikero Probabil că aceasta nu este o discuție grozavă de purtat în comentarii, dar citesc stilul 1 pentru a mă referi la dovezi de forma „Să presupunem că există o mașină PPT care rupe A cu un avantaj neneglijabil. există o mașină PPT care sparge B cu un avantaj neneglijabil. Acest lucru contrazice presupunerea că B este sigur, prin urmare A nu există." În timp ce stilul 2 spune „Luați în considerare o mașină PPT arbitrară. Atunci presupunând că B este sigur, avantajul acestei mașini este neglijabil”.
1
Răspunde
kelalaka avatar
drapel in
kelalaka
Al doilea stil are nevoie de o scriere mai bună de la Titanlord
1
Răspunde
Puncte:1
fgrieu avatar Crypto
drapel ng
fgrieu

Singura diferență pe care o văd între stilul 1 și o redactare adecvată a stilului 2 este că stilului 1 lipsesc lucruri care sunt explicite în 2 despre adversarul/algoritmul presupus să atace B și adversarul/algoritmul rezultat care l-ar ataca pe A:

  1. Algoritmii sunt Probabilistic Polynomial-Time; adică au o intrare implicită cu biți aleatori și rulează cel mult un timp un polinom $P(n)$ pentru toate valorile parametrului de securitate $n$ (sau dimensiunea lor de intrare) peste o limită inferioară.
  2. Au o probabilitate de succes neneglijabilă (sau care nu dispare), adică: pentru un polinom $P'$, pentru orice limită fixă $N\în\mathbb{N}$ exista valori $n>N$ pentru parametrul de securitate (sau dimensiunea lor de intrare), astfel încât probabilitatea de succes să fie de cel puțin $1/P'(n)>0$.

O dovadă că âruperea criptosistemului este la fel de probabil ca ruperea PRGâ demonstrează că în 2 putem reutiliza polinomul $P'$ si valori ale $n$ pentru o limită dată $N$ care sunt adecvate pentru atacul ipotetic al lui B în dovada că atacul lui A este unul care are o probabilitate de succes neneglijabilă.

Cu alte cuvinte, stilul 1 este o simplificare a stilului 2, adesea în detrimentul rigurozității. Pentru unele dovezi în stilul 1, devine stăpânirea stilului 2 pentru a spune cu încredere dacă dovada este corectă.

Există stiluri și mai complexe, de ex. unde probabilitatea de succes este cantitativă.În acest caz, âruperea criptosistemului este la fel de probabil ca ruperea PRGâ este un așa-zis dovadă strânsă. Alte dovezi cantitative sunt mai greu de urmărit.

0 + 0
drapel cn
Maeher
O mașină PPT rulează în timp polinom *strict*, timp polinom *nu* așteptat.
1
Răspunde
drapel cn
Maeher
De asemenea, în 2. ceea ce descrieți este o probabilitate *observabilă*. Acest lucru *nu* este sinonim cu non-negligible.
1
Răspunde
fgrieu avatar
drapel ng
fgrieu
@Maeher: Vă cred pe cuvânt cu privire la definiția PPT și cred că am înțeles și am remediat greșeala mea în definiția non-negligibil. Multumesc pentru corecturi!
0
Răspunde
drapel cn
Maeher
Am încercat să clarific acest aspect. Doar derulați înapoi editarea dacă nu vă place.
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.