Kvantedatamaskiner: slutten av kryptografi?

Annonse

Kvanteberegning er en av disse teknologiene som er så arkane at TV-tegnens navn slipper det når de vil høres smart ut.

Kvanteberegning som idé har eksistert en stund - den teoretiske muligheten ble opprinnelig introdusert av Yuri Manin og Richard Feynman i 1982. I løpet av de siste årene har feltet imidlertid bekymret seg nærmere praktisk.

Selskaper som Google og Microsoft, så vel som offentlige etater som NSA, har alle jaktet kvantecomputere i mange år nå. Et selskap som heter D-Wave har produsert og selger enheter som (mens de ikke er riktige datamaskiner, og kan bare utføre noen få algoritmer) utnytte kvanteegenskaper, og er et annet trinn på veien mot a fullt Turing-komplett Hva er Turing-testen, og vil den noen gang bli slått?Turing-testen er ment å bestemme om maskiner tenker. Har Eugene Goostman-programmet virkelig bestått Turing-testen, eller jukset skaperne rett og slett? Les mer kvantemaskin.

Det virker ikke urimelig å si at det kan forekomme gjennombrudd som gjør at den første storskala kvantecomputeren kan bygges i løpet av et tiår.

Så hvorfor all interessen? Hvorfor skal du bry deg? Datamaskiner blir raskere hele tiden Hva er Moores lov, og hva har det å gjøre med deg? [MakeUseOf Explains]Uflaks har ingenting med Moore's lov å gjøre. Hvis det er foreningen du hadde, forveksler du det med Murphys lov. Imidlertid var du ikke langt unna fordi Moores lov og Murphys lov ... Les mer - hva er så spesielt med kvantemaskiner?

For å forklare hvorfor disse maskinene er så viktige, må vi ta et skritt tilbake og utforske nøyaktig hva kvantecomputere er, og hvorfor de fungerer. For å starte med, la oss snakke om et konsept som heter "runtime complexity."

Hva er Runtime Complexity?

En av de store overraskelsene i informasjonsvitenskapens tidlige dager var oppdagelsen om at hvis du har en datamaskin som løser et problem med en viss størrelse på en viss tid, ved å doble datamaskinens hastighet ikke nødvendigvis la den takle problemer dobbelt så mye stor.

Noen algoritmer øker i den totale gjennomføringstiden veldig, veldig raskt når størrelsen på problemet vokser - noen algoritmer kan raskt fullføres gitt 100 datapunkter, men å fullføre algoritmen gitt 1000 datapunkter ville kreve en datamaskin på jordens størrelse som løper for en milliard år. Runtime-kompleksitet er en formalisering av denne ideen: den ser på kurven for hvor raskt kompleksiteten til et problem vokser, og bruker formen på den kurven for å klassifisere algoritmen.

Generelt uttrykkes disse vanskelighetsklassene som funksjoner. En algoritme som blir proporsjonalt hardere når datasettet som den arbeider med øker (som en enkel tellefunksjon) sies å være en funksjon med en runtime-kompleksitet på "n” (som i, det tar n enheter av tid å behandle n datapunkter).

Alternativt kan det kalles "lineær", fordi når du grafer den, får du en rett linje. Andre funksjoner kan være n ^ 2 eller 2 ^ n eller n! (n factorial). Disse er polynomiale og eksponentielle. I de to sistnevnte tilfellene vokser de eksponentielle så raskt at de i nesten alle tilfeller ikke kan løses for noe annet enn veldig trivielle eksempler.

Runtime Complexity and Cryptography

Hvis du hører disse tingene for første gang, og det høres meningsløst ut, og la oss prøve å begrense denne diskusjonen. Kjøretidskompleksitet er avgjørende for kryptografi, som er avhengig av å gjøre dekryptering mye enklere for folk som kjenner en hemmelig nøkkel enn for de som ikke gjør det. I et ideelt kryptografisk skjema, bør dekryptering være lineær hvis du har nøkkelen, og 2 ^ k (hvor k er antall biter i nøkkelen) hvis du ikke gjør det.

Med andre ord, den beste algoritmen for å dekryptere meldingen uten nøkkel, burde bare være å gjette mulige taster, noe som er umulig for taster som bare er noen hundre biter lange.

For symmetrisk nøkkelkryptografi (hvor de to partiene har sjansen til å utveksle en hemmelighet sikkert før de begynner kommunikasjon) er dette ganske enkelt. For asymmetrisk kryptografi er det vanskeligere.

Asymmetrisk kryptografi, der krypterings- og dekrypteringsnøklene er forskjellige og ikke lett kan beregnes fra hverandre, er en mye vanskeligere matematisk struktur å implementere enn symmetrisk kryptografi, men det er også mye kraftigere: asymmetrisk krypto lar deg ha private samtaler, til og med overappet linjer! Den lar deg også lage “digitale signaturer” slik at du kan bekrefte hvem en melding kom fra, og at den ikke har blitt tuklet med.

Dette er kraftige verktøy, og utgjør grunnlaget for moderne personvern: uten asymmetrisk kryptografi ville brukere av elektroniske enheter ikke ha noen pålitelig beskyttelse mot nysgjerrige øyne.

Fordi asymmetrisk kryptografi er vanskeligere å bygge enn symmetrisk, er ikke standardkrypteringsskjemaene som er i bruk i dag som de kan være: den vanligste krypteringsstandarden, RSA, kan bli sprukket hvis du effektivt kan finne de viktigste faktorene til en veldig stor Antall. Den gode nyheten er at det er et veldig vanskelig problem.

Den mest kjente algoritmen for innregning av store antall i komponentprimene kalles siktet for generelle tallfelt, og har en runtime-kompleksitet som vokser litt tregere enn 2 ^ n. Som en konsekvens må nøklene være omtrent ti ganger lengre for å gi lignende sikkerhet, noe som folk normalt tåler som en kostnad for å drive forretning. Den dårlige nyheten er at hele spillefeltet endres når kvantedatamaskiner kastes i blandingen.

Kvantedatamaskiner: Endring av kryptospillet

Kvantedatamaskiner fungerer fordi de kan ha flere interne tilstander på samme tid, gjennom et kvantefenomen kalt “superposition”. Det betyr at de kan angripe forskjellige deler av et problem samtidig, fordelt på mulige versjoner av universet. De kan også konfigureres slik at grenene som løser problemet havner med mest amplitude, slik at når du åpner boksen på Schrodingers katt, den versjonen av den interne tilstanden du sannsynligvis vil bli presentert for, er en selvglødende katt som holder en dekryptert beskjed.

For mer informasjon om kvantemaskiner, sjekk ut vår nylige artikkel om emnet Hvordan fungerer optiske og kvante datamaskiner?Exascale Age kommer. Vet du hvordan optiske og kvante datamaskiner fungerer, og vil disse nye teknologiene bli vår fremtid? Les mer !

Resultatet av dette er at kvantecomputere ikke bare er lineært raskere, slik normale datamaskiner er: å få to eller ti eller hundre ganger raskere hjelper ikke så mye når det gjelder konvensjonell kryptografi som du er hundrevis av milliarder ganger for treg å behandle. Kvantemaskiner støtter algoritmer som har mindre vekst av tidskompleksiteter enn ellers er mulig. Dette er det som gjør kvantemaskiner grunnleggende forskjellig fra andre fremtidige beregningsteknologier, som grafene og memrister beregning Den siste datateknologien du må se for å troTa en titt på noen av de nyeste datateknologiene som er ment å transformere elektronikken og PC-verdenen de neste årene. Les mer .

For et konkret eksempel kan Shors algoritme, som bare kan kjøres på en kvantecomputer, faktorere store tall i logg (n) ^ 3 tid, som er drastisk bedre enn det beste klassiske angrepet. Å bruke det generelle tallfeltet til å faktorere et tall med 2048 biter tar omtrent 10 ^ 41 tidsenheter, noe som fungerer mer enn en billion billioner billioner. Ved å bruke Shors algoritme tar det samme problemet bare rundt 1000 enheter tid.

Effekten blir mer uttalt jo lenger tastene er. Det er kraften til kvantecomputere.

Misforstå meg ikke - kvantedatamaskiner har mange potensielle ikke-onde bruksområder. Kvantedatamaskiner kan effektivt løse det reisende selgerproblemet, slik at forskere kan bygge mer effektive forsendelsesnettverk og designe bedre kretsløp. Kvantedatamaskiner har allerede kraftig bruk innen kunstig intelligens.

Når det er sagt, vil deres rolle i kryptografi bli katastrofal. Krypteringsteknologiene som lar vår verden fortsette å fungere, avhenger av at helhetsfaktoriseringsproblemet er vanskelig å løse. RSA og relaterte krypteringsordninger er det som lar deg stole på at du er på det rette nettstedet, at filene du har nedlasting er ikke full av skadelig programvare, og at folk ikke spionerer på nettlesingen din (hvis du bruker Tor).

Kryptografi holder bankkontoen din trygg og sikrer verdens kjernefysiske infrastruktur. Når kvantecomputere blir praktiske, slutter all den teknologien å fungere. Den første organisasjonen som utvikler en kvantecomputer, hvis verden fremdeles jobber med teknologiene vi bruker i dag, kommer til å være i en skremmende kraftig posisjon.

Så er kvanteapokalypsen uunngåelig? Er det noe vi kan gjøre med det? Som det viser seg... ja.

Kryptografi etter kvantitet

Det er flere klasser av krypteringsalgoritmer som så vidt vi vet ikke er betydelig raskere å løse på en kvantecomputer. Disse er samlet kjent som post-kvante kryptografi, og gir litt håp om at verden kan overføre til kryptosystemer som vil forbli sikre i en verden av kvantekryptering.

Lovende kandidater inkluderer gitterbasert kryptering, som Ring-Learning With Error, som henter sikkerheten fra et påviselig kompleks maskinlæringsproblem og multivariat kryptografi, som henter sikkerheten fra vanskeligheten med å løse veldig store systemer av enkle ligninger. Du kan lese mer om dette emnet på Wikipedia-artikkelen. Vær forsiktig: mye av dette er komplekst, og du kan oppleve at matematikkbakgrunnen din må økes betydelig før du virkelig kan grave i detaljene.

Takeaway fra mye av dette er at kryptoskjemier etter kvantum er veldig kule, men også veldig unge. De trenger mer arbeid for å være effektive og praktiske, og også for å demonstrere at de er sikre. Årsaken til at vi er i stand til å stole på kryptosystemer er fordi vi har kastet nok klinisk paranoide genier på dem lenge nok at noen åpenbare mangler ville blitt oppdaget nå, og forskere har bevist forskjellige egenskaper som gjør dem sterk.

Moderne kryptografi er avhengig av lys som desinfiseringsmiddel, og de fleste av de kryptografiske ordningene etter kvantum er rett og slett for nye til å stole på verdenssikkerhet til. Men de kommer dit, og med litt hell og litt forberedelser kan sikkerhetseksperter fullføre bryteren før den første kvantecomputeren noensinne kommer på nettet.

Hvis de mislykkes, kan imidlertid konsekvensene være alvorlige. Tanken på at noen har den typen makt er foruroligende, selv om du er optimistisk med tanke på intensjonen deres. Spørsmålet om hvem som først utvikler en fungerende kvantedatamaskin, er et spørsmål som alle bør se veldig nøye når vi flytter inn i det neste tiåret.

Er du bekymret for usikkerheten til kryptografi til kvantecomputere? Hva tar du? Del tankene dine i kommentarene nedenfor!

Bildetillegg: Binær orb Via Shutterstock