Puncte:0

Consecințele P=NP pentru autentificare

drapel ca

Să presupunem că P=NP. Adică, orice problemă a cărei soluție poate fi verificată rapid poate fi, de asemenea, rezolvată rapid, indiferent de ce înseamnă asta la nivel formal. Deci, nu numai P=NP, dar există algoritmi practici în timp polinomial pentru NP- probleme complete. De asemenea, dovada este fie constructivă, fie neconstructivă. Adică, se poate găsi un algoritm pe care, în cele din urmă, l-am găsi suficient de rapid pentru a începe să-l folosim, chiar dacă nu l-am putea dovedi. Apoi devine mult mai greu să păstrezi un secret - o problemă masivă. Ceea ce mă sperie nu ar fi incapacitatea noastră de a ascunde informații, ci incapacitatea noastră de a le dezvălui.

Într-o societate complexă, trebuie să avem încredere în ceilalți, iar ceea ce putem verifica în mod independent nu este suficient. În practică, stabilim încredere cu instituțiile atunci când acestea ne furnizează în mod repetat informații exacte. Nu văd o metodă alternativă, așa că dacă ne pierdem capacitatea de a verifica că primim informații de la o anumită instituție, atunci un impostor ar putea exploata încrederea noastră, ceea ce nu trebuie permis. Prin urmare, nu putem fi suficient de bine informați pentru a avea o societate complexă. P=NP ar distruge autentificarea actuală și, prin urmare, ar reprezenta un risc fundamental dacă nu se găsesc alte soluții.

S-ar putea gasi si alte solutii? Dacă P=NP, avem o lume fără intimitate, dar, reducându-ne pierderile în acest sens, am putea încerca să construim autentificare în jurul acestui fapt. În loc ca entitățile să ne ofere informațiile de care avem nevoie pentru a le identifica, am putea pur și simplu să le strângem din ele. O idee este că, la primirea unui mesaj, vom trimite mesajul nostru care conține unele informații care să ne fie trimise înapoi cu mesajul original, astfel încât să știm că mesajul nostru a fost primit și că cel puțin destinatarul a vrut să trimită originalul. mesaj. Mesajul nostru este spyware, îmbunătățit de algoritmul nostru eficient pentru NP-probleme complete, pe care le folosim pentru a verifica sursa mesajului original.

Puncte:4
drapel ng

Voi încerca să răspund la ceea ce cred că este ceea ce întrebați, și anume:

Dacă $P = NP$, se poate "repara" criptografia prin înlocuirea construcțiilor cu interactiv protocoale?

Aceasta este o întrebare destul de naturală, dar are un răspuns binecunoscut (negativ). Mai exact, orice protocol interactiv care necesită un număr fix (finit) de runde de interacțiune se spune că trăiește într-o clasă de complexitate numită ierarhie polinomială $PH$. Este a priori posibil ca $P = NP$, dar $P \subsetneq PH$. În acest context, răspunsul la întrebarea de mai sus este „da, în principiu” (deși nu cunosc construcții).

Din păcate, unul dintre rezultatele de bază despre $PH$ este că acest lucru este fals, adică $P = NP\implica P= PH$, deci bazează criptografia (într-o lume în care $P = NP$) nu este posibilă numai pentru un număr finit de runde de interactivitate. Există câteva avertismente aici cu protocoale care au $\omega(1)$ runde (acestea sunt într-o clasă de complexitate numită IP), dar acestea ar fi atât de incredibil de lente (din cauza fiecărei runde implică o latență inevitabilă din cauza vitezei luminii) încât nu sunt deosebit de interesante.

Există alte câteva modalități potențiale de a obține (ceva de genul) criptografie într-o lume în care $P = NP$ totusi si anume:

  1. Folosind ipotezele „canal zgomotos”, de exemplu canal de interceptare, și
  2. Utilizarea canalelor cuantice

Ambele au dezavantaje semnificative în comparație cu criptografia teoretică a complexității (pe care nu voi încerca să o rezumam aici), dar valabilitatea lor nu este amenințată de $P = NP$, și sunt probabil lucruri bune de căutat dacă sunteți interesat de posibilitatea unei comunicări sigure într-o lume în care $P = NP$.

Acestea fiind spuse, autentificarea pe computere ar fi mult mai dificilă în general. O altă „soluție” ar fi să te bazezi pe autentificarea personală. Desigur, aici se poate comporta fraudulos, dar este ceva mai dificil de făcut la scară.

Thomas Anton avatar
drapel ca
Autentificarea personală ar dura într-adevăr pe termen lung? Putem deja clona.
drapel cn
Există, de asemenea, abordări precum Criptografia cu granulație fină care nu sunt neapărat afectate de $\mathsf{NP}\subseteq \mathsf{BPP}$.
Mark avatar
drapel ng
@ThomasAnton este greu de prezis, dar formele non-digitale de autentificare sunt mai greu de interpretat milioane de oameni simultan, chiar și având în vedere capacitatea de a clona oameni sau orice altceva.

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.