Bevezetés
1994-ben Peter Shor informatikus felfedezett hogy ha valaha is feltalálnák a kvantumszámítógépeket, azok megtizedelnék az online megosztott információk védelmére használt infrastruktúra nagy részét. Ez az ijesztő lehetőség arra késztette a kutatókat, hogy új, „posztkvantum” titkosítási sémákat hozzanak létre, hogy minél több információt megmentsenek attól, hogy kvantumhackerek kezébe kerüljenek.
Az év elején a Nemzeti Szabványügyi és Technológiai Intézet kiderült négy döntős a kvantum utáni kriptográfiai szabvány keresésében. Közülük hárman „rácsos kriptográfiát” használnak – ezt a sémát a rácsok, a pontok szabályos térbeli elrendezése ihlette.
A rácsos kriptográfia és más posztkvantum lehetőségek alapvetően eltérnek a jelenlegi szabványoktól. De mindegyik a matematikai aszimmetriára támaszkodik. Sok jelenlegi kriptográfiai rendszer biztonsága a szorzáson és a faktoráláson alapszik: Bármely számítógép gyorsan meg tud szorozni két számot, de évszázadokbe telhet, amíg a kriptográfiailag nagy számot beleszámít a fő alkotóelemeibe. Ez az aszimmetria teszi a titkokat könnyen kódolhatóvá, de nehezen dekódolhatóvá.
Shor azt tárta fel 1994-es algoritmusában, hogy a faktoring egy furcsasága sebezhetővé teszi a kvantumszámítógépek támadásával szemben. „Ez egy nagyon specifikus, különleges dolog, amire a kvantumszámítógép képes” – mondta Katherine Stange, matematikus a Colorado Egyetemen, Boulderben. Így Shor után a kriptográfusoknak új munkájuk volt: találjanak olyan matematikai műveletek új halmazát, amelyeket könnyű elvégezni, de szinte lehetetlen visszavonni.
A rácsos kriptográfia az egyik legsikeresebb próbálkozás eddig. Eredetileg az 1990-es években fejlesztették ki, és a pontösszegek visszafejtésének nehézségén alapul.
A rácsos kriptográfia leírásának egyik módja: Képzeld el, hogy a barátodnak van egy rácsa, amely csak egy csomó pont egy szabályos, ismétlődő mintában az egész síkon. A barátod azt akarja, hogy nevezz meg 10 pontot ezek közül. De nehezen megy, és nem fogja kirajzolni az egész rácsot. Ehelyett csak két pontot sorol fel – az elsőt an x-értéke 101 és a y-értéke 19, a másik koordinátákkal [235, 44].
Szerencsére könnyű új pontokat találni egy rácson, mert ha egy rácson lévő két pontot összeadunk és kivonunk, akkor ugyanabban a rácsban egy harmadik pontot kapunk. Tehát nem kell mást tenned, mint összeadni a barátod által adott pontokat, vagy megszorozni egész számokkal, majd összeadni, vagy a kettő valamilyen kombinációját. Tegye ezt nyolc különböző módon, és meg tudja válaszolni barátja kérdését.
But your friend still isn’t satisfied. He gives you the same two starting points, and then asks you if the point [2, 1] is on the same lattice. To answer this question correctly, you have to find the combination of [101, 19] and [235, 44] that produces [2, 1]. This problem is much harder than the first one, and you’ll probably end up just guessing and checking to get the answer.* That asymmetry is what underlies lattice cryptography.
Ha valóban rácsos kriptográfiát szeretne használni információk megosztására, tegye a következőket. Képzelje el, hogy egy barátja (egy kedvesebb!) biztonságos üzenetet szeretne küldeni Önnek. A számok négyzetrácsával kezdi. Tegyük fel, hogy két sora és két oszlopa van, és így néz ki:
Most kitalál egy privát „kulcsot”, amelyet csak te ismersz. Ebben a példában tegyük fel, hogy a privát kulcsa csak két titkos szám: 3 és -2. Az első oszlopban lévő számokat megszorozod 3-mal, a második oszlopban lévőket pedig -2-vel. Adja össze az eredményeket az egyes sorban, hogy egy harmadik oszlopot kapjon két bejegyzéssel.
Ragassza fel az új oszlopot a rács végére. Ez az új háromoszlopos rács az Ön nyilvános kulcsa. Oszd meg szabadon!
(A valós forgatókönyv egy kicsit bonyolultabb lesz. Annak érdekében, hogy a hackerek ne dekódolják a privát kulcsot, egy kis véletlenszerű zajt kell hozzáadnia az utolsó oszlophoz. Itt azonban az egyszerűség kedvéért figyelmen kívül hagyjuk ezt a lépést. )
Most a barátja a nyilvános kulcsot fogja használni, hogy üzenetet küldjön Önnek. Két saját titkos számra gondol: 2-re és 0-ra. Az első sorban lévő számokat megszorozza 2-vel, a második sorban lévőket pedig 0-val. Ezután az egyes oszlopokban lévő eredményeket összeadja, hogy egy harmadik sort kapjon.
Most hozzáerősíti az új sort a rács aljához, és visszaküldi Önnek. (Ismét, egy valós rendszerben némi zajt kell hozzáadnia a sorához.)
Most olvassa el az üzenetet. Ehhez ellenőrizze, hogy barátja utolsó sora helyes-e. Alkalmazza saját privát kulcsát a sor első két bejegyzéséhez. Az eredménynek meg kell egyeznie az utolsó bejegyzéssel.
Barátod dönthet úgy is, hogy az utolsó oszlopban rossz számmal küld egy sort. Tudja, hogy ez a szám nem egyezik a számításaival.
Ha a barátja olyan sort küld, ahol az utolsó szám helyes, akkor ezt 0-ként értelmezi. Ha olyan sort küld, ahol a szám hibás, akkor azt 1-nek fogja értelmezni. A sor tehát egyetlen számot kódol. bit: 0 vagy 1.
Vegye figyelembe, hogy egy külső támadó nem férhet hozzá sem az Ön privát kulcsához, sem az ismerőse kulcsához. Ezek nélkül a támadónak fogalma sem lesz arról, hogy a végső szám helyes-e vagy sem.
A gyakorlatban egy bitnél hosszabb üzeneteket szeretne küldeni. Tehát azok, akik mondjuk egy 100 bites üzenetet szeretnének kapni, 100 új oszlopot generálnak egy helyett. Ezután az üzenet küldője egyetlen új sort hoz létre, módosítva az utolsó 100 bejegyzést úgy, hogy minden bejegyzéshez 0-t vagy 1-et kódoljon.
Ha a rácsos kriptográfiát ténylegesen megvalósítják, akkor számtalan olyan árnyalata lesz, amelyre ez a forgatókönyv nem vonatkozik. Például, ha azt szeretné, hogy az üzenet valóban védve legyen a kíváncsi szemek elől, a mátrixnak elképzelhetetlen számú bejegyzésnek kell lennie, ami annyira nehézkessé teszi az egészet, hogy nem érdemes használni. Ennek megkerülésére a kutatók hasznos szimmetriájú mátrixokat használnak, amelyek csökkenthetik a paraméterek számát. Ezen túlmenően, van egy egész sor finomítás, amely alkalmazható magára a problémára, a hibák beépítésének módjára és még sok másra.
Természetesen mindig lehetséges, hogy valaki végzetes hibát talál a rácsos kriptográfiában, ahogy Shor tette a faktoringban. Nincs garancia arra, hogy egy adott kriptográfiai séma működni fog bármilyen lehetséges támadás esetén. A kriptográfia addig működik, amíg fel nem törik. Valójában a nyár elején az egyik ígéretes posztkvantum kriptográfiai sémát feltörték nem kvantumszámítógép, hanem egy közönséges laptop segítségével. Stange számára az egész projekt egy kényelmetlen paradoxont kelt: „Amit annyira elképesztőnek találok a kriptográfiában, hogy az emberi faj számára építettük ezt az infrastruktúrát azon a szilárd meggyőződésen, hogy emberi képességeink korlátozottak” – mondta. – Annyira elmaradott.
*: The answer, if you’re curious, is 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [vissza a cikkhez]
