A kvantumbiztos algoritmusok témaköre egy viszonylag új terület a kriptográfiában, amit a kvantum számÃtógépek fejlÅ‘dése indukált. Ezek fejlÅ‘dése folyamatosan halad elÅ‘re és bár jelenleg még nem állnak rendelkezésre olyan kvantumszámÃtógépek, amelyek képesek lennének a jelenleg használt titkosÃtási algoritmusok feltörésére. Azonban, hogy ez mikor következik be, az csupán idÅ‘ kérdése. Éppen ezért már most szükséges olyan algoritmusok fejlesztése és alkalmazása, amelyek védettek ezekkel szemben.
De milyen veszélyt is jelentenek ezek a számÃtógépek? A legnagyobb veszélyt az jelenti, hogy egy kvantum számÃtógép a Shor1 algoritmus segÃtéségével képes hatékonyan faktorizálni nagy számokat és megoldani a diszkrét logaritmus problémát. Ezek a problémák alapvetÅ‘ fontosságúak olyan jelenleg használt titkosÃtási rendszerekben, mint az RSA és az elliptikus görbékre épülÅ‘ titkosÃtások.
A másik veszély a Grover2 algoritmusnak köszönhetÅ‘, amely lényegében azt teszi lehetÅ‘vé, hogy egy y = f(x) függvénybÅ‘l x értékét meghatározzuk. Ez nagymértékben felgyorsÃtja a Brute Force támadásokat és az ütközések találását, mivel az algoritmus futási ideje négyzetgyök alapú.
Azonban van megoldás. Szimmetrikus titkosÃtás esetén az AES-GCM kvantum biztosnak számÃt. A kvantum biztosság kérdése leginkább az aszimmetrikus kriptográfiát érinti, mivel jelenleg nincs elfogadott kvantum biztos aszimmetrikus titkosÃtási algoritmus.
Azonban fontosnak tartom kiemelni, hogy van kvantum biztos aszimmetrikus algoritmus, nem is egy. Ezek algoritmusok vagy többváltozós polinomiális problémákra épÃtenek, vagy Lattice alapúak.
A többváltozós polinomiális kriptográfia azon a problémán alapul, hogy a többváltozós polinomiális egyenletek megoldása nagyon nehéz, különösen akkor, ha nagy számú változó és magas fokú polinomok vannak jelen. Ez az algebrai nehézség fennáll a kvantumszámÃtógépek esetén is és a jelenlegi ismeretek szerint nincs hatékony kvantumalgoritmus, amely képes lenne megoldani ezen egyenleteket.
A rács vagy más néven lattice alapú ktiptográfia a rácsok matematikai struktúrájára épül. A rácsok többdimenziós térben elhelyezkedÅ‘, periodikusan ismétlÅ‘dÅ‘ pontok halmazai, amelyek számos nehéz matematikai problémát kÃnálnak, amelyekre a rácsalapú kriptográfiai algoritmusok épÃthetÅ‘ek. Az egyik ilyen a legrövidebb vektor probléma. Ennek a célja megtalálni a legrövidebb nem nulla vektort egy rácsban. Ez egy NP-nehéz probléma és jelenlegi ismereteink alapján ez is ellenáll a kvantum számÃtógépek támadásainak.
A rács alapú megoldások további elÅ‘nye, hogy ezek lehetÅ‘vé teszik a Homomorfikus titkosÃtást is. Ez azt jelenti, hogy a a titkosÃtott adaton műveleteket végezzünk anélkül, hogy felfednnénk az eredeti adatatot.
A jövő
A jövÅ‘t nehéz megjósolni, de aggodalomra és félelemre nincs ok, sÅ‘t további jó hÃr, hogy a könyv tartalma egy darabig releváns marad, mivel jelenleg az RSA 2048 bites variánsa a leggyakrabban alkalmazott kulcs méret. Egy 2022-es cikkben3 megkérdezett szakértÅ‘k véleménye alapján 2037 elÅ‘tt nem valószÃnű, hogy épÃteni tudnánk olyan kvantum számÃtógépet, amely ezt veszélyeztetné.
Ezzel egybevág az NSA ütemterve4 is, amely 2033-ra tervezi a teljes kvantum biztos megoldásokra való átállást.