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

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

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

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

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

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