Algoritam koji će služiti kao kriptografski standard za eru kvantnog računalstva


algoritam matematike

Zasluge: Unsplash/CC0 javna domena

Matematičari često rade u neznanju, a to je vjerojatno zato što malo ljudi, osim kolega matematičara koji dijele istu podspecijalnost, razumije što oni rade. Čak i kada algoritmi imaju praktične primjene, poput pomaganja vozačima da vide automobile koji se približavaju a koje oko ne može razaznati, proizvođač automobila (ili programer njegovog softvera) je taj koji dobiva zasluge.

To se posebno odnosi na kriptografe, neopjevane heroje čiji algoritmi čuvaju sigurnost komunikacije i podataka ljudi kada koriste internet — tehnologiju poznatu kao kriptografija s javnim ključem.

Ali ponekad čista matematika utječe na stvarni svijet. To se dogodilo ovog ljeta kada je Nacionalni institut za standarde i tehnologije odabrao četiri kriptografska algoritma služiti kao standardi za sigurnost javnih ključeva u nadolazećoj eri kvantnih računala, zbog čega će trenutni sustavi šifriranja brzo zastarjeti.

Tri od četiri odabrana algoritma temelje se na radu koji vodi tim matematičara na Brownu: profesori Jeffrey Hoffstein, Joseph Silverman i Jill Pipher (koja također služi kao potpredsjednica Browna za istraživanje).

Priča o podršci NIST-a Falconov algoritam— i NTRU, kriptosustav s javnim ključem na kojem se temelji Falcon — započeo je sredinom 90-ih, kada kvantno računanje još uvijek bio u domeni znanstvene fantastike. U to je vrijeme Hoffsteinov cilj bio razviti algoritam koji bi pojednostavio i ubrzao način rada konvencionalnih kriptografskih algoritama; 1996. je suosnivao NTRU Cryptosystems Inc. sa Silvermanom i Pipherom (koja je također udana za Hoffsteina) kako bi ga izveli na tržište. Hoffstein je rekao da je povijest NTRU-a “saga od koje se ledi krv”, no tvrtka je na kraju bila uspješna, pronašavši odgovarajućeg kupca u Qualcommu. Falcon, koji je Hoffstein zajednički dizajnirao s devet drugih kriptografa, i dva od tri algoritma koje je odabrao NIST, izgrađeni su na izvornom NTRU okviru.

Od prije svog doktorskog studija na MIT-u, preko svih pozicija koje je držao na Institutu za napredne studije, Sveučilište Cambridge, Sveučilište Rochester i Brown, Hoffstein je bio “tip za brojke”, u potpunosti: “Nikad mi nije palo na pamet ne biti matematičar”, rekao je. “Obećao sam sebi da ću se nastaviti baviti matematikom sve dok ne prestane biti zabavno. Nažalost, još uvijek je zabavno!”

Na tragu odabira NIST-a, Hoffstein je opisao svoju transformaciju iz teoretičara brojeva u primijenjenog matematičara s rješenjem za nadolazeći globalni problem od kritične važnosti.

P: Što je kriptografija s javnim ključem?

Kada se povežete s Amazonom da biste obavili kupnju, kako znate da ste stvarno povezani s Amazonom, a ne s lažnom web stranicom koja je postavljena da izgleda točno kao Amazon? Zatim, kada šaljete podatke o svojoj kreditnoj kartici, kako ih poslati bez straha da će biti presretnuti i ukradeni? Prvo pitanje rješava ono što je poznato kao digitalni potpis; drugi se rješava enkripcijom s javnim ključem. Od NIST-ovih standardiziranih algoritama, jedan je za enkripciju s javnim ključem, a ostala tri, uključujući Falcon, za digitalne potpise.

U korijenu toga su problemi čiste matematike vrlo posebne vrste. Teško ih je riješiti (mislite: vrijeme do kraja svemira) ako imate jednu informaciju, a lako ih je riješiti (traje mikrosekunde) ako imate dodatnu tajnu informaciju. Divna stvar je da samo jedna od strana koje komuniciraju – Amazon, u ovom slučaju – mora imati tajni podatak.

P: Koji je sigurnosni izazov koji predstavljaju kvantna računala?

Bez dovoljno jakog kvantnog računala, vrijeme za rješavanje problema šifriranja je eonima. S jakim kvantnim računalom, vrijeme za rješavanje problema svodi se na sate ili manje. Što je još alarmantnije, da je netko posjedovao snažno kvantno računalo, cjelokupna sigurnost interneta potpuno bi se srušila. I Agencija za nacionalnu sigurnost i velike korporacije Klade se da u roku od pet godina postoji dobra šansa da se izgradi kvantno računalo dovoljno snažno da razbije internet.

P: S NTRU rješenjem ste došli početkom do sredine 90-ih, puno prije nego što je itko razmišljao o kriptografskim potrebama potencijalnih kvantnih računala. O čemu ste tada razmišljali?

Smatram da su tri glavna pristupa kriptografiji s javnim ključem vrlo nezgrapna i neestetska. Samo kao jedan primjer, najpoznatija metoda, RSA, uključuje uzimanje brojeva koji imaju više stotina znamenki, zatim njihovo dizanje na potencije koje imaju stotine znamenki, dijeljenje s još jednim brojem koji ima stotine znamenki, i konačno uzimajući ostatak. Ovo je izračunavanje lako izvedivo na računalu, ali nije baš praktično ako imate mali, lagani procesor, poput mobilnog telefona iz 1996. RSA je također vrlo spor—u redu, milisekunde, ali to se i dalje računa kao sporo.

Naš san je bio pronaći metodu za kriptografiju s javnim ključem koja je bila nekoliko redova veličine brža od RSA i mogla bi raditi na uređajima male snage. I uspjeli smo! Ljudi koji su ga implementirali bili su u mogućnosti pokrenuti ga brzinama 200 do 300 puta bržim od RSA. Nisam to učinio sam — opsesivno sam razmišljao o problemu godinu i pol dana, ali nije se pretvorio u rješenje sve dok se nisam pridružio Joeu Silvermanu i Jill Pipher, mojim kolegama iz Browna i suosnivačima NTRU-a .

P: Što znači NTRU?

Nikada nismo rekli — ljudi su jednostavno pretpostavili da mislimo na nešto tehničko i upotrijebili su svoju maštu! Ali to je kratica za “Teoretičari brojeva R Us.” To je iritiralo Jill jer je ona harmonijska analitičarka, a ne teoretičarka brojeva, ali mi je na kraju oprostila.

P: Opisali ste svoj start-up NTRU Cryptosystems kao da imate oko pet iskustava “blizu smrti”. Koji su bili neki od izazova s ​​kojima ste se suočili?

Vratari na terenu uglavnom su kriptografi koji rade za tvrtke iu odjelima računalnih znanosti. Nevjerojatno je teško natjerati da se bilo koji novi algoritam shvati ozbiljno, a posebno je teško ako niste u klubu kriptografa. U našem slučaju, zvonili smo na uzbunu iz dva razloga. Kao prvo, bili smo autsajderi i rešetkama smo dodali dodatnu strukturu iz algebarske teorije brojeva kako bismo stvari učinili učinkovitijima.

Kad god to učinite, postoji ozbiljan rizik da ste slučajno unijeli slabosti. Da, divno je učiniti nešto učinkovitije. Ali jeste li pritom izgubili neki vitalni dio sigurnosti? Potpuno je razumljivo da su ljudi bili duboko sumnjičavi prema ovoj dodatnoj strukturi, koja je uvela mogućnost množenja, ali i zbrajanja. Bilo je potrebno 10 godina intenzivnog ispitivanja prije nego što su ljudi počeli prihvaćati da nisu dodane nikakve slabosti.

P: Ovo nije bila samo akademska vježba. NTRU je bila tvrtka koja je morala raditi s investitorima i potencijalnim kupcima. Rano je NTRU bio nepravedno napadnut u radu koji su napisala neka poznata imena u kriptografiji (koja su kasnije priznala svoju pogrešku). Kako je NTRU to preživio?

Ispostavilo se da je njihov rad uglavnom ignoriran, ali naš je rad bio dovoljno zanimljiv da su svi zaronili u njega. Pokušali su ga napasti i uništiti, i dobio je ogromnu pozornost. Svaku pojedinu površinu koju možete zamisliti opkolili su ovnovi. Zajednica kriptografa bila je toliko otporna na matematičare koji su posegnuli za njihovim područjem. Da nismo bili poznati matematičari iz Browna, ne bismo preživjeli kontroverzu. Na kraju nam je ta pozornost vjerojatno pomogla.

P: Je li postojalo bilo kakvih načina na koje je biti matematičar – autsajder, ovaj svijet – bila prednost?

Ono na što sam najponosniji nije nužno činjenica da je određeni algoritam završio među posljednja četiri odabira NIST-a, iako svaki pojedini od tri algoritma temeljena na rešetki koristi našu prstenastu strukturu (značajka množenja). Svi oni koriste matematiku koju smo uveli jer nakon više od 25 godina proučavanja nije se pojavila niti jedna slabost zbog dodavanja te strukture. Ta matematika, koja je proizašla iz algebarske teorije brojeva, prije nije bila dio kriptografije. To je dio onoga što radim za moj drugi život, i smatram da je posebno divno što smo uspjeli uzeti ovu potpuno apstraktnu teoretsku stvar od naizgled nikakve koristi i pronaći praktičnu primjenu. Kao rezultat toga, sadašnja generacija kriptografa mora poznavati algebarsku teoriju, što je pomalo zabavno.

P: Kako je biti u braku s drugom matematičarkom?

Najblaženija stvar u svemiru je biti u braku s nekim tko razumije kako je to biti matematičar. U matematici, 99,9% vremena provodite sate, tjedne, mjesece i godine razmišljajući o nečemu što ne donosi ništa. Toliko puta mislite da imate fantastičnu ideju, a ona ne ide nikamo. Divno je biti u braku s nekim tko razumije taj osjećaj, čak i ako ne razumijemo uvijek detalje na čemu drugi rade.

P: Ona shvaća kada ste izgubljeni u mislima?

Da, a vjerojatno je i ona.


NIST najavljuje prva četiri kvantno otporna kriptografska algoritma


Citat: Pitanja i odgovori: Algoritam koji će služiti kao kriptografski standard za eru kvantnog računalstva (2022., 22. rujna) preuzeto 23. rujna 2022. s https://phys.org/news/2022-09-qa-algorithm-cryptography-standard-quantum.html

Ovaj dokument podliježe autorskim pravima. Osim poštenog poslovanja u svrhu privatnog proučavanja ili istraživanja, niti jedan dio ne smije se reproducirati bez pismenog dopuštenja. Sadržaj je dat samo u informativne svrhe.