Кванттық қауіп посткванттық криптографияға: AWS алгоритмі торлы стандарттардың тұрақтылығын күмәнға айналдырады
Криптография әлемінде ықтимал тектоникалық ауысым пісіп жетілуде. Amazon Web Services зерттеушісі Дэниел Саймон ұсынған жаңа препринттің менің талдауым посткванттық криптографияның іргетасында жатқан математикалық есептерді шешуді түбегейлі жылдамдата алатын кванттық алгоритмді анықтады. Бұл жай теориялық қызық емес — бұл қазіргі стандарттардың қауіпсіздігі туралы қалыптасқан түсініктерге тікелей сын.
Саймонның басты жаңалығы — оның алгоритмі тапсырма көлемінен орындалу уақытының экспоненциалды емес, полиномиалды тәуелділігін көрсетуінде. Егер бұл нәтиже тәуелсіз тексеруден өтсе, бізге решеткалық криптожүйелердің кванттық есептеулерге төзімділігінің парадигмасын қайта қарауға тура келеді. Дегенмен, атап өту маңызды: бұл ML-KEM немесе ML-DSA сияқты қолданыстағы стандарттарға практикалық шабуыл емес, керісінше әлеуетті олқылықтарды көрсететін теориялық серпіліс.
1990-жылдардағы атақты Шор алгоритмінің ізашары болған өз атындағы алгоритмімен танымал Саймон жаңа жұмысында Dihedral Coset Problem (DCP) мәселесіне назар аударды. Бір қарағанда, DCP әмияндарды немесе қосылыстарды қорғау үшін тікелей қолданылмайды, бірақ дәл осы ол решеткалық криптографияның күрделірек есептеріне байланыстырушы буын болып табылады. Әлі 2000-жылдардың басында Одед Регев DCP тиімді шешімі көпөлшемді решеткалардағы есептердің белгілі бір нұсқаларын бұзуға жол ашатынын дәлелдеді, бірақ ол кезде бұл үшін қол жетпес идеалдандырылған құрал қажет еді.
Саймон қажетті түрлендіруді тікелей кванттық компьютерде орындау арқылы бұл шектеуді айналып өткенін мәлімдейді. Алдыңғы жұмыстармен үйлесімде оның алгоритмі әлеуетті түрде Shortest Vector Problem (SVP) және Learning With Errors (LWE) негізгі есептеріне таралады. Дәл осы есептердің күрделілігіне 2024 жылы қабылданған NIST стандарттарының, оның ішінде ML-KEM және ML-DSA, қауіпсіздігі негізделген. Егер алгоритм расталса, ол кванттық компьютерлердің теориялық тұрғыдан бұл есептерді бұрын болжанғаннан әлдеқайда тиімді шеше алатынын көрсетеді.
Дүрбелең мерзімінен бұрын, бірақ қырағылық міндетті
Дегенмен, мен нарыққа дүрбелеңге берілуге кеңес бермеймін. Саймонның жұмысы нақты параметрлерде ML-KEM кілттерін қалпына келтіру немесе ML-DSA қолтаңбаларын бұрмалау тәсілін көрсетпейді. LWE — бұл есептердің тұтас тобы, ал практикалық стандарттар олардың құрылымдалған нұсқаларын пайдаланады, сондықтан бір класқа арналған нәтиже автоматты түрде барлық жүйелерге таралмайды. Сонымен қатар, препринтте криптографиялық маңызды өлшемдерге шабуыл жасау үшін қажетті ресурстарды — логикалық кубиттерді, вентильдерді және қателерді түзетуді — бағалау жоқ. Тарих қатты мәлімдемелердің күйреген мысалдарын біледі: 2024 жылы зерттеуші Йилей Чэнь LWE үшін полиномиалды алгоритм жариялаған болатын, бірақ оның дәлелінде қате болды және ол өз тұжырымдарынан бас тартты.
Менің кәсіби тұжырымым: бұл препринт — дереу көшуге себеп емес, бірақ криптоиндустрия үшін маңызды сигнал. Біз теориялық ізденістер тез арада нақты қауіптерге айналуы мүмкін дәуірдің табалдырығында тұрмыз. Ұзақ мерзімді қауіпсіздікке тәуелді жобаларға «кванттық сынық» аяқталған фактіге айналғанша күтпей, жаңа, ықтимал төзімдірек криптографиялық примитивтерге өту үшін қазірдің өзінде өз жол карталарына икемділікті енгізу керек.