Kvantedatamaskiner kan knekke kryptering raskere enn forventet med ny algoritme

Kvantedatamaskiner kan knekke kryptering raskere enn forventet med ny algoritme

Tidsstempel: 2. oktober 2023 10:00

En av de mest veletablerte og forstyrrende bruksområdene for en fremtidig kvantedatamaskin er muligheten til å knekke kryptering. En ny algoritme kan redusere barrieren betydelig for å oppnå dette.

Til tross for all hypen rundt kvanteberegning, er det fortsatt betydelige spørsmålstegn rundt omkring hva kvantedatamaskiner faktisk vil være nyttige for. Det er håp om at de kan akselerere alt fra optimaliseringsprosesser til maskinlæring, men hvor mye enklere og raskere de vil være er fortsatt uklart i mange tilfeller.

En ting er imidlertid ganske sikkert: En tilstrekkelig kraftig kvantedatamaskin kan gjøre våre ledende kryptografiske systemer verdiløse. Mens de matematiske gåtene som ligger til grunn for dem er praktisk talt uløselige av klassiske datamaskiner, ville de være helt håndterbare for en stor nok kvantedatamaskin. Det er et problem fordi disse ordningene sikrer det meste av informasjonen vår på nettet.

Redningsgraden har vært at dagens kvanteprosessorer er langt unna den typen skala som kreves. Men ifølge a rapportere inn Vitenskap, New York University dataforsker Oded Regev har oppdaget en ny algoritme som kan redusere antallet qubits som kreves betydelig.

Tilnærmingen omarbeider i hovedsak en av de mest vellykkede kvantealgoritmene til dags dato. I 1994 utviklet Peter Shor ved MIT en måte å finne ut hvilke primtall som må multipliseres sammen for å gi et bestemt tall - et problem kjent som primtall.

For store tall er dette et utrolig vanskelig problem som raskt blir vanskelig å løse på konvensjonelle datamaskiner, og det er derfor det ble brukt som grunnlag for den populære RSA-krypteringsordningen. Men ved å dra nytte av kvantefenomener som superposisjon og sammenfiltring, kan Shors algoritme løse disse problemene selv for utrolig store tall.

Det faktum har ført til ikke liten mengde panikk blant sikkerhetseksperter, ikke minst fordi hackere og spioner kan samle opp krypterte data i dag og så bare vente på utviklingen av tilstrekkelig kraftige kvantedatamaskiner til å knekke dem. Og selv om post-kvantekrypteringsstandarder er utviklet, kan det ta mange år å implementere dem på nettet.

Men det blir nok ganske lang ventetid. De fleste implementeringer av RSA er avhengige av minst 2048-biters nøkler, som tilsvarer et tall på 617 sifre. Fujitsu-forskere nylig beregnet at det ville ta en fullstendig feiltolerant kvantedatamaskin med 10,000 104 qubits XNUMX dager å knekke et så stort tall.

Regevs nye algoritme, beskrevet i en pre-print publisert på arXiv, kan potensielt redusere disse kravene betydelig. Regev har i hovedsak omarbeidet Shors algoritme slik at det er mulig å finne et talls hovedfaktorer ved å bruke langt færre logiske trinn. Å utføre operasjoner i en kvantedatamaskin innebærer å lage små kretser fra noen få qubits, kjent som porter, som utfører enkle logiske operasjoner.

I Shors opprinnelige algoritme er antallet porter som kreves for å faktorisere et tall kvadratet på antall biter som brukes til å representere det, som er betegnet som n2. Regevs tilnærming ville bare kreve n1.5 porter fordi den søker etter primfaktorer ved å utføre mindre multiplikasjoner av mange tall i stedet for veldig store multiplikasjoner av et enkelt tall. Det reduserer også antallet porter som kreves ved å bruke en klassisk algoritme for å behandle utdataene videre.

I papiret anslår Regev at for et 2048-bits tall kan dette redusere antallet porter som kreves med to til tre størrelsesordener. Hvis det er sant, kan det gjøre det mulig for mye mindre kvantedatamaskiner å knekke RSA-kryptering.

Det er imidlertid praktiske begrensninger. Til å begynne med bemerker Regev at Shors algoritme drar nytte av en rekke optimaliseringer utviklet gjennom årene som reduserer antallet qubits som kreves for å kjøre den. Det er ennå uklart om disse optimaliseringene vil fungere på den nye tilnærmingen.

Martin Ekerå, en kvantedataforsker ved den svenske regjeringen, fortalte også Vitenskap at Regevs algoritme ser ut til å trenge kvanteminne for å lagre mellomverdier. Forutsatt at minnet vil kreve ekstra qubits og spise inn alle beregningsfordeler det har.

Ikke desto mindre er den nye forskningen en betimelig påminnelse om at når det gjelder kvantedatabehandlings trussel mot kryptering, målstengene beveger seg hele tiden, og overgang til post-kvante ordninger kan ikke skje raskt nok.

Bilde Credit: Google

Kvantedatamaskiner kan knekke kryptering raskere enn forventet med den nye algoritmen PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Tidstempel:

Mer fra Singularity Hub