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