Алгоритм на решетках назвали лидером постквантовой криптографии ( 1 фото )

research.ibm.com

Национальный институт стандартов и технологий США (NIST) представил результаты второго раунда стандартизации протоколов постквантовой криптографии, где выделил алгоритм на решетках. Он одновременно потенциально пригоден для полномасштабного внедрения и при этом квантово-устойчивый. Отчет опубликован на сайте NIST.

Квантовый компьютер интересен исследователям не только потому, что он может имитировать сложные физически системы, но и потому, что он может взломать многие протоколы криптографии. Алгоритм Шора, например, способен взломать очень популярный криптографический алгоритм RSA. Один из способов защиты от квантового компьютера — это поменять протоколы шифрования данных, перейдя на квантовую криптографию, в которой для передачи информации используются квантовые системы. Проблема перехода заключается в том, что необходимо менять системы шифрования на физическом уровне. Другой способ — это постквантовая криптография, в которой используются классические системы и задачи, но такие сложные, что их неспособен решить даже квантовый компьютер.

В прошлом году компания Google впервые решила задачу, недоступную классическому суперкомпьютеру, но эта задача очень далека от взлома криптографических систем. Более того, квантовым компьютерам потребуется не один год, чтобы дойти до уровня, когда можно будет взломать хотя бы старые системы, где используется слабая криптография. Однако важно понимать, что как только появится квантовый компьютер, будет уже поздно менять криптографию, поэтому стандартизация новых протоколов происходит сейчас.

В 2016 году американский Национальный институт стандартов и технологий запустил конкурс, в котором различные исследовательские центры разрабатывали методы квантово-устойчивой криптографии. Результаты конкурса, который проводится с целью выработать стандарт шифрования, будут объявлены в 2022 году, но уже сейчас стало известно, что среди предложенных подходов появился фаворит: постквантовая криптография на решетках.

Этот подход основан на задаче дискретной оптимизации, а именно на поиске самого короткого пути на многомерной решетке. В то время как другие задачи дискретной оптимизации, такие как разложение большого числа на простые множители, решаются квантовым компьютером за полиномиальное время, на сегодняшний день неизвестно ни одного квантового алгоритма, который способен решить задачу на решетке за время меньше экспоненциального.

Безусловно, существует много задач, где квантовый компьютер не дает преимущества, однако для полномасштабного перехода необходимо реализовать решение, которое легко внедрить в современные криптографические системы. Хоть поиск пути на решетке невероятно трудная задача, с помощью нее можно быстро сгенерировать защищенный ключ. Более того, в процессе генерации не затрачивается много памяти, для работы небольших маломощных устройств.

Про то, в каком состоянии находится универсальный квантовый компьютер, читайте в нашем материале «У кого кубитов больше», а подробнее про квантовую криптографию вы можете узнать в материале «Квантовые технологии».

Михаил Перельштейн