Sokszor hallani, hogy a kvantumszámítógépek lényegében mindenre képesek lesznek. Ezek helyenként erősen túlzó állítások, mindenesetre tény, hogy komoly veszélyt jelentenek majd az online kommunikációra. Mit jelent ez pontosan, mennyire kell félnünk tőlük, és hogyan próbálnak védekezni a kriptográfusok?

Mit jelent a biztonságos kommunikáció? Erre a kérdésre teljes egészében nem fogunk válaszolni, de egy némileg egyszerűsített modellt azért bemutatunk. Képzeljük el, hogy két fél kommunikál az online térben (emailt, WhatsApp-üzenetet küld, vagy a bankkártyával fizet). Az egyik fél szeretne üzenetet küldeni a másiknak, lehetőleg úgy, hogy egy harmadik fél ne kapjon semmilyen információt az üzenet tartalmáról. Ehhez egy biztonságos csatornára lenne szükség, de az internet működéséből adódóan nem biztonságos, hiszen minden adat csomagokra darabolva, sok köztes gépen (router, szerver, szolgáltató) halad keresztül, és egy támadónak számos ponton lehetősége nyílik arra, hogy hozzáférjen. Ezért tehát az adat titkosítására van szükség.

Itt máris komoly problémába ütközünk. Ha a titkosítást úgy képzeljük el, mint egy ládika, amihez tartozik egy kulcs, akkor felmerül a kérdés: kinél van a kulcs? Ha csak az egyik félnél lenne, akkor a kommunikáció csak egy irányba működne, tehát valamilyen módon mindkét félnek rendelkeznie kell ugyanazzal a közös kulccsal, amellyel az üzeneteket titkosítani és visszafejteni lehet. Ahhoz, hogy ezt biztonságosan meg lehessen oldani, kitalálták az úgynevezett kulcscsere-protokollokat, amik nagyon trükkös matematikai eljárások, és fontos építőkövei a biztonságos kommunikációnak. A kulcscsere-protokollok lényege, hogy mindkét félnek van egy titkos kulcsa, amit csak az egyikük ismer, és egy nyilvános kulcsa, amit mindeketten ismernek. Összesen tehát négy kulcs segítségével tudnak közösen előállítani egy ötödik kulcsot, amivel majd a kommunikáció ténylegesen zajlani fog.

A másik fontos építőkő az úgynevezett autentikáció. Szeretnénk meggyőződni arról, hogy valóban azzal kommunikálunk, akivel szeretnénk. Ha kapunk egy emailt, hogy fizessünk be bírságként 100 ezer forintot egy bankszámlára, szeretnénk tudni, hogy a levél legitim szervezettől érkezett, és nem egy csalótól. Ezt általában úgynevezett digitális aláírásokkal oldjuk meg, ahol egy bitsorozat köti össze a korábban említett nyilvános kulcsunkat az üzenettel és az aláírással. Autentikációval és kulcscserével már nagyon sokfajta kommunikációt képesek vagyunk kivitelezni a fenti paradigma szerint.

Min múlik ezeknek az eljárásoknak a biztonsága, vagyis az, hogy illetéktelenek nem tudják lehallgatni az üzeneteinket, illetve hogy nem tudják hamisítani az aláírásainkat? Jelenleg minden ilyen protokoll biztonsága valamilyen algoritmikus probléma megoldásának nehézségétől függ. Ezeket az eljárásokat szándékosan úgy tervezték, hogy a biztonságuk egy-egy jól ismert, nehéz matematikai problémára épüljön. Ez azt jelenti, hogy ha valaki fel akarná törni a rendszert, olyan feladatot kellene elvégeznie, amit a mai számítógépek észszerű időn belül nem tudnak megoldani.

Klasszikus példa erre, hogy nagyon nehéz nagy egész számokat prímtényezőkre bontani. Ez a probléma, a faktorizáció már az ókori görögök óta foglalkoztatja a matematikusokat, és bár azóta sok részletben történt előrelépés, a mai napig senki nem talált rá igazán hatékony, úgynevezett polinomiális algoritmust. Polinomiális algoritmus alatt azt értjük, hogy a futási idő a szám nagyságával együtt nő, de csak valamilyen hatvány szerint (például az idővel arányosan vagy négyzetesen), nem pedig exponenciálisan, ahol a szükséges idő a szám méretével robbanásszerűen megnő.

Itt jön a képbe a kvantumszámítógép. Peter Shor amerikai informatikus 1994-ben mutatott be egy kvantumszámítógépen polinomiális időben futtaható algoritmust, ami képes egész számokat prímtényezőkre bontani. Az ötlet a perióduskeresésen az úgynevezett kvantumos Fourier-transzformáción alapul. Itt fontos újra megemlíteni, hogy a kvantumszámítógép nem varázsdoboz, nem old meg mindent mágikusan, de az egész számok faktorizációjához szorosan kapcsolódó periódusszámolás valóban nagyon jól illik a kvantumszámítógép profiljába.

Ez akkor azt jelenti, hogy a kvantumszámítógép megöli az online kommunikációt, és feltöri a jelszavaimat? Nem feltétlenül. Először is a jelszavainkra nemigen lesz hatással, ugyanis azokat teljesen más technológia védi, az úgynevezett kriptográfiai hash-függvények. Itt maximum arra lehet szükség, hogy kicsit hosszabb jelszavakat válasszunk, de ez semmilyen problémával nem jár. Az online kommunikáció már bonyolultabb kérdés, de itt fontos megjegyezni, hogy egyszerűen annyi történt, hogy az emberiség a rossz lóra tett, amikor faktorizáció- és diszkrétlogaritmus-alapú sémákat választott. Annyi a teendő, hogy új sémákat kell tervezni, amelyek olyan nehéz problémákon alapulnak, amelyek megoldására nem létezik hatékony kvantumalgoritmus.

Ezt a tudományágat kvantumrezisztens vagy poszt-kvantum kriptográfiának nevezzük (az utóbbi kifejezés Daniel J. Bernstein amerikai kriptográfustól származik). A tudományág egyébként meglepően régóta létezik, körülbelül 50 éves múltra tekint vissza, ugyanis az első ilyen sémát egy szintén amerikai informatikus, Robert McEliece alkotta meg. Itt érdekességként megjegyzendő, hogy akkor még a kvantumszámítógép elméleti modellje sem létezett, tehát őt egyszerűen csak a biztonságos titkosítás motiválta, nem a kvantumrezisztencia. A témakör Shor 1994-es cikke után futott fel, és azóta nagyon sok kutatónak ez a fő kutatási területe (köztük e sorok írójának is).

Ahogy már említettük, a feladat új, nehéz matematikai problémák megalkotása. Ugyanakkor fontos szempont, hogy ha valaki megadja a probléma megoldását — ami gyakorlatilag a titkos kulcs —, akkor gyorsan lehessen ellenőrizni, hogy az valóban helyes-e. A prímtényezőkre bontás esetében ez azt jelenti, hogy bár a nagy számok faktorizációja rendkívül nehéz, ha valakinek megmondják prímtényezőket, villámgyorsan tudja ellenőrizni, hogy a szorzatuk valóban az adott szám-e. Ez biztosítja a gyakorlatban, hogy a feltörés nehéz, de a kulcs birtokában a dekódolás gyors legyen, ami fontos gyakorlati szempont. No de nézzük, melyek azok a problémák, amik jelenleg a kvantumszámítógépek számára is nehéznek tűnnek.