Посткванттық қауіпсіздік әлемін Amazon Web Services (AWS) зерттеушісі Дэниел Саймон ұсынған жаңа ғылыми жұмыс дүр сілкіндірді. Жаңа препринтте ол қазіргі посткванттық стандарттардың негізінде жатқан негізгі математикалық есептерді полиномиалдық күрделілікпен шешуге қабілетті кванттық алгоритмді сипаттайды — яғни оның жұмыс уақыты есептің көлемінің дәрежесі ретінде өседі, бұрын ойлағандай экспоненциалды емес.

Егер бұл нәтиже дұрыс болып шықса, ол решеткалық криптографияның кванттық есептеулерге төзімділігі туралы түсінігімізді түбегейлі қайта қарауы мүмкін. Дегенмен, маңыздысын атап өту керек: құжатта ML-KEM (кілттерді инкапсуляциялау механизмі) немесе ML-DSA (цифрлық қолтаңбалар) сияқты қолданыстағы стандарттарға практикалық шабуыл жоқ. Бұл әлі тексерілуі тиіс теориялық серпіліс туралы мәселе.

Алгоритмнің мәні және оның решеткалармен байланысы

1990-жылдардағы атақты Шор алгоритмінің ізашары болған өз аттас алгоритмімен танымал Саймон жаңа жұмысында диэдрлік көршілес кластар мәселесіне (Dihedral Coset Problem, DCP) назар аударды. Жеңілдетілген түрде, кванттық компьютер байланысқан күйлер жиынтығын алады және олардың арасындағы жасырын мәнді анықтауы керек. DCP өзі шифрлау үшін тікелей қолданылмайды, бірақ 2000-жылдардың басында математик Одед Регев DCP тиімді шешімі көпөлшемді решеткалардағы есептердің белгілі бір нұсқаларына, соның ішінде Shortest Vector Problem (SVP) және Learning With Errors (LWE) шабуыл жасауға мүмкіндік беретінін дәлелдеді.

Регев тәсілінің басты шектеуі басқа күрделі есепті шешу үшін идеалдандырылған құралдың қажеттілігі болды. Саймон қажетті түрлендіруді тікелей кванттық компьютерде орындау арқылы бұл кедергіні айналып өте алғанын мәлімдейді. Бұл 2024 жылы қабылданған NIST стандарттарының негізіне алынған LWE құрылымдық нұсқаларын жеделдетілген шешуге жол ашуы мүмкін.

Дүрбелең мерзімінен бұрын: ненің сыртында қалды

Дауысты тақырыптарға қарамастан, Саймонның жұмысы ML-KEM бұзуды немесе ML-DSA қолтаңбасын жалғандауды көрсетпейді. Зерттеуші нақты криптографиялық параметрлерге шабуыл жасамады, ал оның алгоритмінде практикалық іске асыру үшін қажетті логикалық кубиттер саны, кванттық вентильдер немесе қателерді түзету операциялары туралы бағалау жоқ. Сонымен қатар, LWE — бұл есептердің тұтас тобы, және бір класқа арналған нәтиже өнеркәсіпте қолданылатын барлық құрылымдық нұсқаларға автоматты түрде таралмайды.

Ғылыми қоғамда решеткаларға арналған полиномиалдық кванттық алгоритмдер туралы дауысты мәлімдемелер тексеруден өте алмаған прецеденттер болған. Мысалы, 2024 жылы зерттеуші Йилей Чэнь осыған ұқсас серпіліс туралы мәлімдеді, бірақ бірнеше күннен кейін оның дәлелдемесінен өлімге әкелетін қате табылды және ол өз тұжырымдарынан бас тартты. Қазіргі уақытта Саймонның жұмысы бойынша тәуелсіз консенсус жоқ, және бұл қорытынды жасауға әлі ерте екенінің басты көрсеткіші.

Менің талдауым: Бұл препринт — өнеркәсіп үшін маңызды сигнал, бірақ дүрбелеңге себеп емес. Ол біздің қазіргі теориялық қауіпсіздік модельдеріміздің осалдығын көрсетеді. Саймонның алгоритмі дұрыс болса да, практикалық қауіпке дейін — ондаған жылдар. Дегенмен, криптоқоғам гибридті схемаларға көшуді және посткванттық алгоритмдерді әртараптандыруды жеделдетуі керек, бүкіл қауіпсіздікті бір математикалық негізге қоймау үшін.