Noua Matematică a Criptografiei Cuantice
În teorie, fizica cuantică poate ocoli problemele matematice dificile care stau la baza criptării moderne. O nouă demonstrație arată cum.
Versiunea originală a acestei povești a apărut în Quanta Magazine.
Problemele dificile nu sunt, de obicei, binevenite. Dar criptografii le iubesc. Asta pentru că anumite probleme matematice dificile stau la baza securității criptării moderne. Orice truc inteligent pentru a le rezolva va distruge majoritatea formelor de criptografie.
Cu câțiva ani în urmă, cercetătorii au găsit o abordare radical nouă a criptării, care nu are acest punct slab potențial. Abordarea exploatează caracteristicile specifice ale fizicii cuantice. Dar, spre deosebire de schemele anterioare de criptare cuantică, care funcționează doar pentru câteva sarcini speciale, noua abordare poate realiza o gamă mult mai largă de sarcini. Și ar putea funcționa chiar dacă toate problemele aflate în centrul criptografiei „clasice” obișnuite s-ar dovedi ușor de rezolvat.
Dar această descoperire izbitoare s-a bazat pe ipoteze nerealiste. Rezultatul a fost „mai mult o dovadă de concept”, a declarat Fermi Ma, cercetător în criptografie la Institutul Simons pentru Teoria Calculului din Berkeley, California. „Nu este o declarație despre lumea reală.”
Acum, o nouă lucrare a doi criptografi a pus bazele unui drum către criptografia cuantică fără aceste ipoteze ciudate. „Această lucrare spune că, dacă anumite alte conjecturi sunt adevărate, atunci criptografia cuantică trebuie să existe”, a spus Ma.
Castel în cer
Vă puteți gândi la criptografia modernă ca la un turn cu trei părți esențiale. Prima parte este roca de bază adânc sub turn, care este făcută din probleme matematice dificile. Turnul în sine este a doua parte – acolo puteți găsi protocoale criptografice specifice care vă permit să trimiteți mesaje private, să semnați documente digitale, să exprimați voturi secrete și multe altele. Între ele, asigurând acele aplicații de zi cu zi la roca de bază matematică, se află o fundație făcută din blocuri de construcție numite funcții unidirecționale. Ele sunt responsabile pentru asimetria inerentă oricărei scheme de criptare.
„Este unidirecțională deoarece puteți cripta mesaje, dar nu le puteți decripta”, a spus Mark Zhandry, criptograf la NTT Research.
În anii 1980, cercetătorii au dovedit că criptografia construită pe funcții unidirecționale ar asigura securitatea pentru multe sarcini diferite. Dar, zeci de ani mai târziu, încă nu sunt siguri că roca de bază este suficient de puternică pentru a o susține. Problema este că roca de bază este făcută din probleme dificile speciale – cunoscute tehnic sub numele de probleme NP – a căror caracteristică definitorie este că este ușor să verifici dacă orice soluție candidat este corectă. (De exemplu, împărțirea unui număr în factorii săi primi este o problemă NP: greu de făcut pentru numere mari, dar ușor de verificat.) Multe dintre aceste probleme par intrinsec dificile, dar oamenii de știință în domeniul calculatoarelor nu au reușit să o demonstreze. Dacă cineva descoperă un algoritm ingenios pentru a rezolva rapid cele mai dificile probleme NP, roca de bază se va prăbuși, iar întregul turn se va prăbuși.
Din păcate, nu vă puteți muta pur și simplu turnul în altă parte. Fundația turnului – funcțiile unidirecționale – poate sta doar pe o rocă de bază a problemelor NP. Pentru a construi un turn pe probleme mai dificile, criptografii ar avea nevoie de o nouă fundație care să nu fie făcută din funcții unidirecționale.
Acest lucru a părut imposibil până acum câțiva ani, când cercetătorii și-au dat seama că fizica cuantică ar putea ajuta. Totul a început cu o lucrare din 2021 a unui student absolvent pe nume William Kretschmer, care a atras atenția asupra unei probleme ciudate despre proprietățile sistemelor cuantice. Cercetătorii au arătat curând că problema lui Kretschmer ar putea înlocui funcțiile unidirecționale ca fundație pentru un nou turn de protocoale criptografice. În anul următor, Kretschmer și alții au dovedit că această abordare alternativă ar putea funcționa chiar și fără probleme NP dificile. Dintr-o dată, părea că ar putea fi posibilă construirea unei fortărețe criptografice care să fie mult mai robustă.
Dar unde să-l construim? Problema cuantică pe care Kretschmer a folosit-o ca fundație a implicat dispozitive de calcul ipotetice numite oracole care pot răspunde instantaneu la întrebări specifice. Oracolele pot fi instrumente teoretice utile, dar nu există de fapt. Dovezile lui Kretschmer au fost ca un plan pentru construirea unui castel în cer. Exista o modalitate de a-l aduce pe pământ?
A doua fundație
În toamna anului 2022, această întrebare a atras atenția lui Dakshita Khurana, un criptograf de la Universitatea Illinois din Urbana-Champaign și NTT Research. Khurana și studentul ei absolvent Kabir Tomer au pornit să construiască un nou turn de criptografie. Primul ei pas a fost să construiască o nouă fundație folosind blocuri de construcție cuantice în loc de funcții unidirecționale clasice. Apoi ar trebui să demonstreze că această nouă fundație ar putea susține un turn de alte protocoale criptografice. Odată ce a dovedit că fundația poate susține turnul, ar trebui să găsească un loc solid pentru ca întregul lucru să se așeze – o rocă de bază a problemelor din lumea reală care par și mai dificile decât problemele NP utilizate în criptografia clasică.
Pentru primul pas, Khurana și Tomer s-au concentrat pe o versiune cuantică a unei funcții unidirecționale, numită generator de stare unidirecțional, care a satisfăcut cele trei proprietăți care fac funcțiile unidirecționale utile. În primul rând, funcția trebuie să ruleze rapid, astfel încât să puteți genera cu ușurință o blocare criptografică și cheia corespunzătoare pentru a o deschide pentru fiecare mesaj pe care doriți să îl trimiteți. În al doilea rând, fiecare blocare trebuie să fie sigură, necesitând un efort mare pentru a se sparge fără cheia potrivită. În cele din urmă, fiecare blocare trebuie să fie ușor de deschis cu cheia potrivită.
Diferența crucială constă în natura încuietorilor. Funcțiile clasice unidirecționale generează încuietori matematice realizate din biți – 0 și 1 care stochează informații într-un computer clasic. Generatoarele cuantice de stare unidirecționale ar genera în schimb încuietori formate din unități de informații cuantice numite qubiți. Aceste încuietori cuantice ar putea rămâne sigure chiar dacă toate încuietorile clasice sunt ușor de spart.
Khurana și Tomer au sperat să înceapă cu această nouă fundație cuantică și să construiască un turn de protocoale criptografice deasupra ei. „Acest lucru s-a dovedit a fi destul de greu”, a spus Khurana. „Am rămas blocați timp de multe, multe luni.”
„Încercăm doar să înțelegem acest nou peisaj.” Mark Zhandry
Până în iulie 2023, Khurana era însărcinată de aproape nouă luni și plănuia să intre în concediu parental. Tomer nu mai avea idei. „Sunt mult mai pesimist decât Dakshita”, a spus el. „Ea este întotdeauna cea care crede că lucrurile vor funcționa.”
Apoi au făcut o descoperire. Pasul crucial a fost definirea unui alt bloc de construcție matematic care a servit ca un fel de etaj de subsol: o structură care ar conecta fundația generatoarelor de stare unidirecționale la un turn de protocoale criptografice. Când Khurana și Tomer au calculat ce proprietăți ar trebui să aibă acel bloc de construcție, au descoperit că seamănă cu o funcție unidirecțională cu un amestec uluitor de caracteristici cuantice și clasice. Ca și într-o funcție unidirecțională obișnuită, atât încuietorile, cât și cheile erau făcute din biți clasici, dar procedura de generare a acestor încuietori și chei ar rula doar pe un computer cuantic.
Și mai ciudat, noul bloc de construcție a satisfăcut primele două proprietăți definitorii ale funcțiilor unidirecționale, dar nu și pe a treia: a fost ușor să generezi încuietori și chei și fiecare încuietoare a fost greu de spart. Dar o cheie nu și-ar deschide cu ușurință încuietoarea. Khurana și Tomer au numit aceste noi blocuri de construcție uluitoare puzzle-uri unidirecționale.
Intuitiv, este greu de imaginat cum ar putea fi utile: la ce folosește o cheie pe care nu o poți folosi niciodată? Dar cei doi criptografi au arătat că puzzle-urile unidirecționale combinate cu alte trucuri cuantice ar permite de fapt multe protocoale criptografice. Dacă puteți genera încuietori și chei care se potrivesc în principiu, nu contează dacă procedura de deblocare este extrem de ineficientă.
„Doar să știi că există un algoritm care poate fi arbitrar de lent este suficient”, a spus Kretschmer, care este acum cercetător la Institutul Simons. „Acest lucru este foarte surprinzător.”
Cu acea piesă lipsă la locul ei, au terminat rapid demonstrația pe 4 august. Fiica lui Khurana s-a născut doar câteva zile mai târziu.
Înregistrare permanentă
Până în noiembrie, Khurana s-a întors la muncă și era gata să încerce a doua fază a planului ei. Ea și Tomer au arătat că multe tipuri de criptografie pot fi construite pe puzzle-uri unidirecționale și că puzzle-urile unidirecționale pot fi construite la rândul lor pe o nouă fundație cuantică formată din generatoare de stare unidirecționale. Următorul pas din planul lor inițial a fost să conecteze acea fundație cuantică la o nouă rocă de bază – un set relativ invincibil de probleme matematice care sunt chiar mai dificile decât cele din NP.
Dar, pe măsură ce Khurana și Tomer s-au luptat cu acea sarcină, au decis să adopte o abordare mai directă: uitați de generatoarele de stare unidirecționale și, în schimb, ancorați puzzle-urile unidirecționale direct pe roca de bază matematică.
Dintr-o perspectivă, aceasta a părut o alegere ciudată. Puzzle-urile unidirecționale erau ciudățenii matematice pe care Khurana și Tomer le folosiseră într-un pas intermediar al demonstrației lor. Cu toate acestea, puzzle-urile unidirecționale aveau unele avantaje. Pentru un lucru, deși sunt cuantice, încuietorile și cheile pe care le generează sunt clasice. Khurana a crezut că acest lucru ar putea face mai ușor conectarea lor la o rocă de bază a matematicii clasice.
În plus, puzzle-urile unidirecționale generează chei care sunt prea greoaie pentru a deschide încuietori. Acest lucru ar putea face mai ușor conectarea lor la probleme atât de complicate încât chiar și verificarea soluțiilor pare fără speranță.
Dar ce probleme specifice ar funcționa? Khurana avea un candidat în minte: calcularea unei combinații specifice de intrări într-un tabel de numere numit matrice. Această problemă, cunoscută sub numele de problema permanentă a matricei, este notoriu de dificil de rezolvat pentru matrice mari și nu există o modalitate simplă de a verifica dacă un calcul este corect. Problema permanentă a matricei are, de asemenea, alte proprietăți matematice speciale pe care criptografii le consideră atractive. „Aceasta ar fi o problemă frumoasă pe care să bazezi criptografia”, a spus Khurana.
Problema permanentă a matricei se conectează, de asemenea, la o altă problemă pe care computerele cuantice o pot rezolva cu ușurință, dar computerele clasice aparent nu o pot face. Cercetătorii lucrează la demonstrarea acestui avantaj computațional cuantic într-un sens teoretic precis. Khurana și Tomer au arătat că o astfel de demonstrație le-ar permite, de asemenea, să construiască puzzle-uri unidirecționale sigure – și astfel întregul turn al criptografiei cuantice – deasupra problemei permanente.
„Ei au reușit să facă acest lucru din aceste ipoteze bine studiate”, a spus Kretschmer. „Am fost foarte bucuros să văd asta.”
Cu noul lor rezultat, Khurana și Tomer au redus efectiv două probleme deschise la una. Dacă cercetătorii finalizează demonstrația că computerele cuantice le depășesc cu adevărat pe cele clasice într-o sarcină specifică, aceasta va pune automat criptografia cuantică pe un teren teoretic mult mai puternic decât practic orice fel de criptografie clasică.
Din păcate, nu veți putea folosi noua abordare a lui Khurana și Tomer pentru a trimite mesaje secrete în curând. În ciuda progreselor recente, tehnologia de calcul cuantic nu este încă suficient de matură pentru a pune în practică ideile lor. Între timp, alți cercetători au conceput metode de criptare cuantică care ar putea fi utilizate mai devreme, deși vor fi necesare mai multe lucrări pentru a stabili că sunt cu adevărat sigure.
Criptografia cuantică s-a dovedit deja plină de surprize, iar cercetătorii au început de curând să exploreze posibilitățile. „Încercăm doar să înțelegem acest nou peisaj care a existat cu adevărat tot timpul”, a spus Zhandry.
Poveste originală retipărită cu permisiunea Quanta Magazine, o publicație editorial independentă a Fundației Simons, a cărei misiune este de a spori înțelegerea publică a științei prin acoperirea evoluțiilor și tendințelor de cercetare în matematică și științele fizice și ale vieții.