Nova matematika kvantne kriptografije

Izvorna verzija od ova priča pojavio se u Magazin Quanta.

Teški problemi obično nisu dobrodošli vid. Ali kriptografi ih vole. To je zato što određeni tvrdi matematički problemi podupiru sigurnost modernog šifriranja. Svaki pametan trik za njihovo rješavanje propadat će većinu oblika kriptografije.

Prije nekoliko godina istraživači su otkrili Radikalno novi pristup šifriranju Kome nedostaje ovo potencijalno slabo mjesto. Pristup koristi neobične značajke kvantne fizike. Ali za razliku od ranijih shema kvantne šifriranja, koje djeluju samo za nekoliko posebnih zadataka, novi pristup može postići mnogo širi raspon zadataka. I to bi moglo funkcionirati čak i ako se svi problemi u središtu uobičajene “klasične” kriptografije pokaže lako rješivim.

Ali ovo upečatljivo otkriće oslanjalo se na nerealne pretpostavke. Rezultat je bio “više dokaz koncepta”, rekao je Fermi Maistraživač kriptografije iz Instituta Simons za teoriju računanja u Berkeleyu u Kaliforniji. “To nije izjava o stvarnom svijetu.”

A sad, a novi papir Dva kriptografa postavila su put do kvantne kriptografije bez onih neobičnih pretpostavki. “Ovaj rad kaže da ako su određene druge pretpostavke istinite, tada mora postojati kvantna kriptografija”, rekao je Ma.

Dvorac na nebu

Modernu kriptografiju možete smatrati toranjom s tri osnovna dijela. Prvi dio je podloga duboko ispod tornja, koja je izrađena od tvrdog matematičkih problema. Sam toranj je drugi dio – možete pronaći određene kriptografske protokole koji vam omogućuju slanje privatnih poruka, potpisati digitalne dokumente, bacati tajne glasačke listiće i još mnogo toga.

Između toga, osiguravanje tih svakodnevnih prijava na matematički podloga, temelj je izrađen od građevnih blokova zvanih Jednosmjerne funkcije. Oni su odgovorni za asimetriju svojstvenu bilo kojoj shemi šifriranja. “To je jednosmjerno jer možete šifrirati poruke, ali ne možete ih dešifrirati”, rekao je Mark Zhandrykriptograf u NTT Research.

U 1980-ima, istraživači su dokazali da će kriptografija izgrađena na jednosmjernim funkcijama osigurati sigurnost za više različitih zadataka. Ali desetljećima kasnije, oni još uvijek nisu sigurni da je podloga dovoljno jaka da ga podrži. Problem je u tome što je podloga izrađena od posebnih teških problema – tehnički poznatih kao NP problemi – čiji je značajka definiranja u tome što je lako provjeriti je li bilo koje rješenje kandidata ispravno. (Na primjer, razbijanje broja na svoje glavne faktore problem je NP: teško je učiniti za veliki broj, ali lako je provjeriti.)

Mnogi od ovih problema izgledaju intrinzično teški, ali računalni znanstvenici nisam uspio dokazati. Ako netko otkrije genijalni algoritam za brzo rješavanje najtežih problema s NP -om, podloga će se raspasti, a cijeli će toranj srušiti.

Nažalost, ne možete jednostavno premjestiti svoj toranj negdje drugdje. Temelj kule-jedno vrijeme-može samo sjediti na temelju problema s NP-om.

Da bi izgradili toranj na težim problemima, kriptografima će trebati novi temelj koji nije napravljen od jednosmjernih funkcija. To se činilo nemogućim tek prije samo nekoliko godina, kada su istraživači shvatili da kvantna fizika može pomoći.