Az ünnepelt kriptográfiai algoritmus frissítést kapott | Quanta Magazin

Egyre digitalizálódó életünkben a biztonság a kriptográfián múlik. Küldjön privát üzenetet vagy fizessen számlát online, és Ön olyan algoritmusokra hagyatkozik, amelyek célja adatai titokban tartása. Természetesen egyesek fel akarják fedni ezeket a titkokat – ezért a kutatók azon dolgoznak, hogy teszteljék ezeknek a rendszereknek az erejét, hogy megbizonyosodjanak arról, hogy nem omlanak össze egy ügyes támadó kezeitől.

Ennek a munkának az egyik fontos eszköze az LLL algoritmus, amely azokról a kutatókról kapta a nevét, akik közzétette 1982-ben — Arjen Lenstra, Hendrik Lenstra Jr. és Lovász László. Az LLL, számos leszármazottjával együtt, bizonyos esetekben megtörheti a kriptográfiai sémákat; viselkedésük tanulmányozása segít a kutatóknak olyan rendszereket tervezni, amelyek kevésbé sebezhetőek a támadásokkal szemben. Az algoritmus adottságai pedig túlmutatnak a kriptográfián: hasznos eszköz a fejlett matematikai területeken is, például a számítási számelméletben.

Az évek során a kutatók az LLL változatait csiszolták, hogy gyakorlatiasabbá tegyék a megközelítést – de csak egy bizonyos pontig. Most egy kriptográfuspár új LLL-stílusú algoritmust épített fel, amely jelentősen megnövelte a hatékonyságot. Az új technika, amely megnyerte a A legjobb papír díja a 2023-as Nemzetközi Kriptológiai Konferencia, kibővíti azon forgatókönyvek körét, amelyekben az informatikusok és matematikusok megvalósíthatóan alkalmazhatják az LLL-szerű megközelítéseket.

„Igazán izgalmas volt” – mondta Chris Peikert, a Michigani Egyetem kriptográfusa, aki nem vett részt a dolgozatban. Az eszköz évtizedek óta a kutatások középpontjában áll – mondta. „Mindig jó, ha egy olyan célpont, amelyen oly régóta dolgoznak… azt mutatja, hogy még mindig várhatunk meglepetéseket.”

Az LLL típusú algoritmusok a rácsok világában működnek: szabályosan elhelyezkedő pontok végtelen gyűjteményeiben. Ennek egyik módjaként képzelje el, hogy padlót burkol. Fedheti négyzet alakú csempékbe, és ezeknek a lapoknak a sarkai egy rácsot alkotnának. Alternatív megoldásként választhat egy másik csempe formát – mondjuk egy hosszú paralelogrammát – egy másik rács létrehozásához.

Egy rács az „alapja” segítségével írható le. Ez vektorok halmaza (lényegében számlisták), amelyeket különböző módon kombinálhat, hogy a rács minden pontját megkapja. Képzeljünk el egy rácsot, amelynek bázisa két vektorból áll: [3, 2] és [1, 4]. A rács csak az összes pont, amelyet a vektorok másolatainak összeadásával és kivonásával érhet el.

Ez a vektorpár nem az egyetlen alapja a rácsnak. Minden legalább kétdimenziós rácsnak végtelen sok lehetséges alapja van. De nem minden bázis egyenlő. Az a bázis, amelynek vektorai rövidebbek és közelebb állnak egymáshoz, általában könnyebben használhatók, és hasznosabbak bizonyos számítási problémák megoldásában, ezért a kutatók ezeket a bázisokat „jónak” nevezik. Példa erre az alábbi ábrán látható kék vektorpár. A hosszabb és kevésbé ortogonális vektorokból álló bázisok – mint a piros vektorok – „rossznak” tekinthetők.

Ez a munka az LLL számára: Adj neki (vagy testvéreinek) egy többdimenziós rács alapját, és kiköp egy jobbat. Ezt a folyamatot rácsalapú redukciónak nevezik.

Mi köze ennek az egésznek a kriptográfiához? Kiderült, hogy a kriptográfiai rendszer feltörésének feladata bizonyos esetekben egy másik problémaként újraírható: viszonylag rövid vektort kell találni egy rácsban. És néha ez a vektor kivehető az LLL-stílusú algoritmus által generált redukált bázisból. Ez a stratégia segített a kutatóknak olyan rendszereket megdönteni, amelyeknek látszólag kevés közük van a rácsokhoz.

Elméleti értelemben az eredeti LLL algoritmus gyorsan fut: a futáshoz szükséges idő nem skálázódik exponenciálisan a bemenet méretével – azaz a rács méretével és a számok méretével (bitekben) bázisvektorok. De polinomiális függvényként növekszik, és „ha valóban meg akarjuk csinálni, a polinomidő nem mindig olyan megvalósítható” – mondta. Léo Ducas, a holland CWI nemzeti kutatóintézet kriptográfusa.

A gyakorlatban ez azt jelenti, hogy az eredeti LLL algoritmus nem tudja kezelni a túl nagy bemeneteket. „A matematikusok és a kriptográfusok többre vágytak” – mondta Keegan Ryan, a San Diego-i Kaliforniai Egyetem doktorandusza. A kutatók azon dolgoztak, hogy optimalizálják az LLL-stílusú algoritmusokat, hogy alkalmazkodjanak a nagyobb bemenetekhez, és gyakran jó teljesítményt érjenek el. Ennek ellenére néhány feladat makacsul elérhetetlen maradt.

Az új lap, amelynek szerzője Ryan és tanácsadója, Nadia Heninger, több stratégiát kombinál az LLL-stílusú algoritmus hatékonyságának javítása érdekében. Egyrészt a technika rekurzív struktúrát használ, amely a feladatot kisebb részekre bontja. Másrészt az algoritmus gondosan kezeli az érintett számok pontosságát, egyensúlyt találva a sebesség és a helyes eredmény között. Az új munka lehetővé teszi a kutatók számára, hogy több ezer dimenzióval redukálják a rácsok alapjait.

A korábbi munkák hasonló megközelítést követtek: A 2021 papír a rekurziót és a precíziós kezelést is kombinálja a nagy rácsok gyors működéséhez, de csak bizonyos típusú rácsoknál működött, és nem mindegyiknél, amelyek fontosak a kriptográfiában. Az új algoritmus sokkal szélesebb tartományban is jól működik. „Nagyon örülök, hogy valaki megtette” – mondta Thomas Espitau, a PQShield cég kriptográfiai kutatója és a 2021-es verzió szerzője. Csapata munkája „a koncepció bizonyítékát” kínálta – mondta; az új eredmény azt mutatja, hogy „nagyon gyors rácsredukciót végezhet hangos módon”.

Az új technika már kezdett hasznosnak bizonyulni. Aurel Page, az Inria francia nemzeti kutatóintézet matematikusa elmondta, hogy csapatával az algoritmus adaptációját alkalmazták néhány számítási számelméleti feladat elvégzésére.

Az LLL-stílusú algoritmusok szerepet játszhatnak a rácsos kriptográfiai rendszerekkel kapcsolatos kutatásokban is. biztonságban maradjanak még a jövőben is nagy teljesítményű kvantumszámítógépekkel. Nem jelentenek veszélyt az ilyen rendszerekre, mivel lebontásukhoz rövidebb vektorokat kell találni, mint amennyit ezek az algoritmusok képesek elérni. A kutatók által ismert legjobb támadások azonban LLL-stílusú algoritmust használnak „alapvető építőelemként” – mondta. Wessel van Woerden, a Bordeaux-i Egyetem kriptográfusa. A támadások tanulmányozására irányuló gyakorlati kísérletekben ez az építőelem mindent lelassíthat. Az új eszköz segítségével a kutatók kibővíthetik a támadási algoritmusokon futtatható kísérletek körét, így tisztább képet adnak a teljesítményükről.

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket számítástechnikai olvasói felmérés és ingyenesen nyerhetsz Quanta áru.