A kvantumszámítógépek a vártnál hamarabb feltörhetik a titkosítást az új algoritmussal

Újra kiadta Platón

Követő: 0

A jövőbeni kvantumszámítógépek egyik legbevált és legzavaróbb felhasználási módja a titkosítás feltörésének képessége. Egy új algoritmus jelentősen csökkentheti ennek elérését.

A kvantumszámítás körüli felhajtás ellenére még mindig vannak jelentős kérdőjelek mire lesznek valójában hasznosak a kvantumszámítógépek. Vannak remények, hogy mindent felgyorsíthatnak az optimalizálási folyamatoktól a gépi tanulásig, de az, hogy mennyivel lesznek könnyebbek és gyorsabbak, sok esetben nem világos.

Egy dolog azonban egészen biztos: egy kellően erős kvantumszámítógép értéktelenné teheti vezető kriptográfiai sémáinkat. Míg az őket alátámasztó matematikai rejtvények a klasszikus számítógépek számára gyakorlatilag megoldhatatlanok, egy elég nagy kvantumszámítógép számára teljesen megoldhatók lennének. Ez azért probléma, mert ezek a rendszerek az online információink nagy részét védik.

A megmentő kegyelem az volt, hogy a mai kvantumprocesszorok nagyon messze vannak a szükséges méretektől. De szerint a jelentést in Tudomány, A New York-i Egyetem informatikusa, Oded Regev felfedezett egy új algoritmust, amely jelentősen csökkentheti a szükséges qubitek számát.

A megközelítés lényegében az eddigi egyik legsikeresebb kvantumalgoritmust dolgozza át. 1994-ben Peter Shor az MIT-nél kidolgozott egy módszert annak meghatározására, hogy mely prímszámokat kell összeszorozni egy adott szám létrehozásához – ezt a problémát prímfaktoringnak nevezik.

Nagy számok esetén ez egy hihetetlenül nehéz probléma, amely gyorsan megoldhatatlanná válik a hagyományos számítógépeken, ezért ezt használták a népszerű RSA titkosítási séma alapjául. De az olyan kvantumjelenségek előnyeit kihasználva, mint a szuperpozíció és az összefonódás, a Shor-algoritmus még hihetetlenül nagy számok esetén is képes megoldani ezeket a problémákat.

Ez a tény nem kis pánikot keltett a biztonsági szakértők körében, nem utolsósorban azért, mert a hackerek és kémek manapság titkosított adatokat gyűjthetnek össze, majd egyszerűen megvárják a kellően erős kvantumszámítógépek fejlesztését, hogy feltörjék azokat. És bár posztkvantum titkosítási szabványokat fejlesztettek ki, ezek megvalósítása az interneten sok évig tarthat.

Bár valószínű, hogy sokáig várni kell. Az RSA legtöbb megvalósítása legalább 2048 bites kulcsokra támaszkodik, ami egy 617 számjegy hosszúságú számnak felel meg. Fujitsu kutatók nemrég számolták ki hogy egy teljesen hibatűrő, 10,000 104 qubites kvantumszámítógépnek XNUMX napra lenne szüksége egy ekkora szám feltöréséhez.

Regev új algoritmusa azonban, amelyet az a nyomtatás előtti megjelenés dátuma arXiv, potenciálisan jelentősen csökkentheti ezeket a követelményeket. Regev lényegében úgy dolgozta át Shor algoritmusát, hogy sokkal kevesebb logikai lépéssel meg lehessen találni egy szám prímtényezőit. A kvantumszámítógépben végzett műveletek során néhány qubitből kis áramköröket, úgynevezett kapukat hoznak létre, amelyek egyszerű logikai műveleteket hajtanak végre.

Shor eredeti algoritmusában a szám faktorálásához szükséges kapuk száma a reprezentációhoz használt bitek számának négyzete, amelyet a következőképpen jelölünk. n². Regev megközelítése csak megkövetelné n^1.5 kapuk, mert prímtényezőket keres több szám kisebb szorzásával, nem pedig egyetlen szám nagyon nagy szorzásával. Csökkenti a szükséges kapuk számát is, ha klasszikus algoritmust használ a kimenetek további feldolgozásához.

A cikkben Regev becslése szerint egy 2048 bites szám esetén ez két-három nagyságrenddel csökkentheti a szükséges kapuk számát. Ha ez igaz, akkor sokkal kisebb kvantumszámítógépek képesek feltörni az RSA titkosítást.

Vannak azonban gyakorlati korlátok. Regev először is megjegyzi, hogy a Shor algoritmusa számos, az évek során kifejlesztett optimalizálás előnyeit élvezi, amelyek csökkentik a futtatásához szükséges qubitek számát. Egyelőre nem világos, hogy ezek az optimalizálások működnének-e az új megközelítésben.

Martin Ekerå, a svéd kormány kvantumszámítógép-kutatója is elmondta Tudomány hogy úgy tűnik, hogy Regev algoritmusának kvantum memóriára van szüksége a közbenső értékek tárolásához. Feltéve, hogy a memória extra qubiteket igényel, és felemészti az összes számítási előnyét.

Mindazonáltal az új kutatás időszerű emlékeztető arra, hogy amikor a kvantumszámítástechnika titkosítási veszélyéről van szó, a kapufák folyamatosan mozognak, és a kvantum utáni sémákra való átállás nem történhet meg elég gyorsan.

Kép: Google