Kvantitietokoneet: Salauksen loppuminen?

Mainos

Kvanttilaskenta on yksi niistä tekniikoista, jotka ovat niin kaarevia, että TV-hahmojen nimet pudottavat sen, kun he haluavat kuulostaa älykkäältä.

Kvanttilaskenta ideana on ollut olemassa jo jonkin aikaa - teoreettisen mahdollisuuden esittelivät alun perin Yuri Manin ja Richard Feynman vuonna 1982. Viime vuosina kenttä on kuitenkin edistynyt huolestuttavasti lähempänä käytännöllisyyttä.

Yritykset kuten Google ja Microsoft, samoin kuin valtion virastot, kuten NSA, ovat kaikki kuumeisesti ajaneet kvanttitietokoneita jo vuosia. D-Wave-niminen yritys on tuottanut ja myy laitteita, jotka (vaikka ne eivät ole oikeita tietokoneita, ja voivat) suorita vain muutama algoritmi) hyödyntämään kvanttiominaisuuksia ja ovat toinen askel askeleella kohti tietä täysin Turing-täydellinen Mikä on Turing-testi ja aikooko se koskaan lyödä?Turingin testi on tarkoitettu selvittämään, ajattelevatko koneet. Läpäissytkö Eugene Goostman -ohjelma todella Turingin testin vai huijasivatko tekijät vain? Lue lisää kvanttikone.

Ei vaikuta kohtuuttomalta sanoa, että voi tapahtua läpimurtoja, jotka sallivat ensimmäisen suuren mittakaavan kvantitietokoneen rakentamisen kymmenen vuoden kuluessa.

Joten miksi kaikki kiinnostuksen kohteet? Miksi sinun pitäisi välittää? Tietokoneet nopeutuvat koko ajan Mikä on Mooren laki ja mitä sillä on sinun kanssasi? [MakeUseOf selittää]Huonolla onnella ei ole mitään tekemistä Mooren lain kanssa. Jos se on yhdistys, joka sinulla oli, sekoitat sen Murphyn lakiin. Et kuitenkaan olleet kaukana, koska Mooren laki ja Murphyn laki ... Lue lisää - Mikä on erityistä kvantitietokoneissa?

Selittääksemme miksi nämä koneet ovat niin tärkeitä, joudumme ottamaan askel taaksepäin ja tutkimaan tarkalleen, mitkä kvantitietokoneet ovat ja miksi ne toimivat. Aloitetaan puhumme käsitteestä, jonka nimi on “runtime monimutkaisuus”.

Mikä on Runtime Complexity?

Yksi tietotekniikan alkuaikojen suurimmista yllätyksistä oli havainto, että jos sinulla on tietokone, joka ratkaisee tietyn koon tietyssä ajassa, tietokoneen nopeuden kaksinkertaistaminen ei välttämättä anna sen ratkaista ongelmia kahdesti iso.

Jotkut algoritmit lisäävät kokonaissuoritusaikaa hyvin, hyvin nopeasti ongelman koon kasvaessa - jotkut algoritmit voidaan nopeasti suorittaa loppuun annetulle 100 datapisteelle, mutta annetun 1000 datapisteen algoritmin suorittaminen vaatisi maapallon kokoista tietokonetta, joka toimii miljardilla vuotta. Suorituksenajan monimutkaisuus on tämän idean muodollinen muoto: se tarkastelee käyrää siitä, kuinka nopeasti ongelman monimutkaisuus kasvaa, ja käyttää kyseisen käyrän muotoa algoritmin luokittelemiseen.

Yleensä nämä vaikeusluokat ilmaistaan ​​funktioina. Algoritmin, joka muuttuu suhteellisesti vaikeammaksi, kun tietojoukon toiminta lisääntyy (kuten yksinkertaisen laskentatoiminnon), sanotaan olevan toiminto, jonka ajonaikaisuus on "n” (kuten vuonna, se vie n aikayksiköt prosessoitavaksi n datapisteet).

Vaihtoehtoisesti sitä voidaan kutsua ”lineaariseksi”, koska kuvaajana saat suoran viivan. Muut toiminnot saattavat olla n ^ 2 tai 2 ^ n tai n! (n tekijä). Nämä ovat polynomia ja eksponentiaalisia. Kahdessa viimeksi mainitussa tapauksessa eksponentiaaliset kasvavat niin nopeasti, että melkein kaikissa tapauksissa niitä ei voida ratkaista mihinkään paitsi hyvin triviaalisiin esimerkkeihin.

Suorituksenaikainen monimutkaisuus ja salaus

Jos kuulet näitä juttuja ensimmäistä kertaa ja se kuulostaa merkityksettömältä ja epämääräiseltä, yritämme perustaa tämä keskustelu. Suorituksenajan monimutkaisuus on kriittisen tärkeätä salaustekniikan kannalta, mikä perustuu salauksen avaamisen helpottamiseen salaisen avaimen tuntevien ihmisten kuin niiden, jotka eivät tiedä. Ihanteellisessa salaustekniikassa salauksen purkamisen tulisi olla lineaarista, jos sinulla on avain, ja 2 ^ k (missä k on avaimessa olevien bittien lukumäärä), jos et.

Toisin sanoen, parhaan algoritmin sanoman salauksen purkamiseksi ilman avainta pitäisi olla yksinkertaisesti arvaaminen mahdollisista avaimista, mikä on houkuttelematon vain muutaman sadan bitin pituisille avaimille.

Symmetrisen avaimen salaus (jossa molemmilla osapuolilla on mahdollisuus vaihtaa salaisuus turvallisesti ennen viestinnän aloittamista) on melko helppoa. Epäsymmetrisen salauksen suhteen se on vaikeampaa.

Epäsymmetrinen salaus, jossa salaus- ja salausavaimet ovat erilaisia ​​ja joita ei voida helposti laskea toisistaan, on paljon vaikeampi matemaattinen rakennetta toteutettavaksi kuin symmetrinen salaustekniikka, mutta se on myös paljon tehokkaampi: epäsymmetrinen krypto antaa sinun pitää yksityisiä keskusteluja jopa napautettuina linjat! Sen avulla voit myös luoda ”digitaalisia allekirjoituksia”, jotta voit tarkistaa, keneltä viesti tuli ja ettei sitä ole käsitelty.

Nämä ovat tehokkaita työkaluja ja muodostavat nykyaikaisen yksityisyyden perustan: Ilman epäsymmetristä kryptografiaa elektronisten laitteiden käyttäjillä ei olisi luotettavaa suojaa uteliailta silmiltä.

Koska epäsymmetristä salausta on vaikeampi rakentaa kuin symmetristä, nykyään käytössä olevat vakiosalausjärjestelmät eivät ole yhtä vahvoja sellaisena kuin ne voisivat olla: yleisin salausstandardi, RSA, voidaan murtaa, jos löydät tehokkaasti erittäin suuren määrä. Hyvä uutinen on, että se on erittäin vaikea ongelma.

Tunnetuinta algoritmia suurten lukumäärien laskemiseksi niiden komponenttimääriksi kutsutaan yleiseksi lukukenttäseulaksi, ja sen suorituksen monimutkaisuus kasvaa hieman hitaammin kuin 2 ^ n. Seurauksena on, että avainten on oltava noin kymmenen kertaa pidempiä samanlaisen turvallisuuden tarjoamiseksi, jota ihmiset yleensä sietävät liiketoiminnan kustannuksina. Huono uutinen on, että koko toimintakenttä muuttuu, kun kvantitietokoneet joutuvat sekoitukseen.

Quantum Computers: Kryptopelin vaihtaminen

Kvantitietokoneet toimivat, koska niillä voi olla useita sisäisiä tiloja samanaikaisesti kvantti-ilmiön, jota kutsutaan ”superpositioksi”. Tämä tarkoittaa, että he voivat hyökätä ongelman eri osiin samanaikaisesti, jakautuen maailmankaikkeuden mahdollisiin versioihin. Ne voidaan myös konfiguroida siten, että ongelmat ratkaisevat haarat kääntyvät suurimmalla amplitudilla, niin että kun avaat laatikon Schrodinger's kissan versio sisäisestä tilasta, joka sinulle todennäköisimmin esitetään, on savun näköinen kissa, jolla on salaus viesti.

Katso lisätietoja kvantitietokoneista viime artikkeli aiheesta Kuinka optiset ja kvantitietokoneet toimivat?Exascale-aika on tulossa. Tiedätkö kuinka optiset ja kvantitietokoneet toimivat, ja tuleeko näistä uusista tekniikoista tulevaisuutta? Lue lisää !

Tämän tuloksena on, että kvantitietokoneet eivät ole vain lineaarisesti nopeampia, normaalien tietokoneiden tapa: saada kaksi tai kymmenen tai sata kertaa nopeampi ei auta paljon, kun kyseessä on tavanomainen salaus, jonka prosessointi on satoja miljardeja kertoja liian hidas. Kvantitietokoneet tukevat algoritmeja, joiden kasvava ajoaika on monimutkaisempaa kuin muuten on mahdollista. Tämän vuoksi kvantitietokoneet eroavat pohjimmiltaan muista tulevaisuuden laskennallisista tekniikoista, kuten grafeenin ja muistiinlaskenta Uusin tietotekniikka, joka sinun täytyy nähdä uskoaksesiTutustu uusimpaan tietotekniikkaan, joka on asetettu muuttamaan elektroniikan ja tietokoneiden maailmaa seuraavien vuosien aikana. Lue lisää .

Konkreettisena esimerkkinä Shorin algoritmi, joka voidaan suorittaa vain kvantitietokoneella, voi vaikuttaa suureen määrään loki (n) ^ 3 aika, joka on huomattavasti parempi kuin paras klassinen hyökkäys. Yleisen lukukenttäseulan käyttäminen 2048 bittiä olevan luvun kerroittamiseen vie noin 10 ^ 41 aikayksikköä, mikä on enemmän kuin biljoonaa biljoonaa biljoonaa biljoonaa. Shorin algoritmia käyttämällä sama ongelma vie vain noin 1000 yksikköä aikaa.

Vaikutus käy selvemmin, mitä kauemmin näppäimet ovat. Se on kvantitietokoneiden voima.

Älä ymmärrä minua väärin - kvantitietokoneilla on paljon potentiaalista ei-pahaa käyttöä. Kvantitietokoneet voivat ratkaista matkustavien myyjien ongelman tehokkaasti, jolloin tutkijat voivat rakentaa tehokkaampia lähetysverkkoja ja suunnitella parempia piirejä. Kvantitietokoneilla on jo tehokas käyttö tekoälyyn.

Niiden rooli salaustekniikassa tulee kuitenkin katastrofaaliseksi. Salaustekniikat, joiden avulla maailmamme voi toimia edelleen, riippuvat siitä, onko kokonaislukukertoitusongelmia vaikea ratkaista. RSA ja siihen liittyvät salausjärjestelmät antavat sinun luottaa siihen, että olet oikealla verkkosivustolla, että tiedostot lataus ei ole täynnä haittaohjelmia ja että ihmiset eivät vakoile Internet-selailusi (jos käytät Tor).

Salaaminen pitää pankkitilisi turvassa ja turvaa maailman ydininfrastruktuurin. Kun kvantitietokoneet tulevat käytännöllisiksi, kaikki tämä tekniikka lakkaa toimimasta. Ensimmäinen organisaatio, joka kehittää kvantitietokonetta, jos maailma toimii edelleen nykyisellä tekniikalla, tulee olemaan pelottavan voimakkaassa asemassa.

Joten onko kvantti-apokalypsi väistämätön? Voimmeko tehdä asialle jotain? Kuten käy ilmi... kyllä.

Postkvantti-salaus

On olemassa useita luokkia salausalgoritmeja, joita tiedämme siltä osin, etteivät ne ole merkittävästi nopeampia ratkaisemaan kvantitietokoneella. Näitä kutsutaan yhdessä kvantin jälkeiseksi kryptografiaksi, ja ne tarjoavat jonkin verran toivoa, että maailma voi siirtyä kryptosysteemeihin, jotka pysyvät turvassa kvanttisalauksen maailmassa.

Lupaaviin ehdokkaisiin sisältyy hilapohjainen salaus, kuten Ring-Learning With Error, joka johtaa turvallisuuteensa todistettavasti monimutkaisesta koneoppimisongelma ja monimuuttujainen salaus, joka johtaa sen turvallisuuteen vaikeudesta ratkaista erittäin suuria yksinkertaisten järjestelmiä yhtälöt. Voit lukea lisää aiheesta aiheesta Wikipedia-artikkeli. Varo: suuri osa näistä asioista on monimutkaista, ja saatat huomata, että matematiikan taustasi on syytä lisätä huomattavasti, ennen kuin voit todella syventää yksityiskohtia.

Usein tästä tapahtuu se, että postkvanttikryptoskeemit ovat erittäin viileitä, mutta myös hyvin nuoria. He tarvitsevat enemmän työtä ollakseen tehokkaita ja käytännöllisiä ja osoittaen myös turvallisuutensa. Syynä siihen, että pystymme luottamaan kryptosysteemeihin, on se, että olemme heittäneet niihin riittävän kauan kliinisiä paranoisia geenejä että kaikki ilmeiset puutteet olisi jo havaittu, ja tutkijat ovat osoittaneet erilaisia ​​piirteitä, jotka tekevät niistä vahva.

Nykyaikainen salaustekniikka riippuu valosta desinfiointiaineena, ja suurin osa postikvanttisista kryptografioista on yksinkertaisesti liian uusia luottamaan maailman turvallisuuteen. He ovat kuitenkin saapumassa sinne, ja pienellä onnella ja valmistelulla tietoturva-asiantuntijat voivat suorittaa kytkimen loppuun ennen kuin ensimmäinen kvantitietokone koskaan tulee verkkoon.

Jos ne epäonnistuvat, seuraukset voivat kuitenkin olla vakavia. Ajatus keneltä tahansa sellaisesta vallasta on järkyttävää, vaikka olet optimistinen heidän aikomuksensa suhteen. Kysymys siitä, kuka ensin kehittää toimivan kvantitietokoneen, on sellainen, jota kaikkien tulisi tarkkailla erittäin tarkkaan siirtyessämme seuraavaan vuosikymmeneen.

Oletko huolissasi kryptografian epävarmuudesta kvantitietokoneissa? Mitä otat? Jaa ajatuksesi alla olevissa kommenteissa!

Kuvapisteet: Binaarinen pallo Shutterstockin kautta