Квантовые компьютеры взломают любой шифр: в США создали новый алгоритм, но есть нюанс

Ученый-компьютерщик из Нью-Йоркского университета Одед Регев придумал алгоритм, который ускорит количество кубитов, необходимых квантовому компьютеру для взлома любого шифрования. Об этом пишет портал Singularity Hub.

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

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

Хотя, сейчас, для имеющихся квантовых компьютеров это все равно относительно долгая задача. Дело в том, что большинство реализаций шифрования RSA полагаются на ключи длиной не менее 2048 бит, что эквивалентно числу длиной 617 цифр. Исследователи Fujitsu недавно подсчитали, что полностью отказоустойчивому квантовому компьютеру с 10 000 кубитами потребуется 104 дня, чтобы взломать такое большое число.

Важно

Загадочный 4D-метаматериал поможет развитию квантовых вычислений: что придумали ученые

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

В исходном алгоритме Шора количество элементов, необходимых для факторизации числа, равно квадрату числа бит, используемых для его представления, которое обозначается как n2. Подход Регева потребует всего n1,5 вентилей, поскольку он ищет простые множители, выполняя меньшие умножения многих чисел, а не очень большие умножения одного числа. Это также уменьшает количество элементов, необходимых за счет использования классического алгоритма для дальнейшей обработки выходных данных.

В статье Регев подсчитал, что для 2048-битного числа это может сократить количество необходимых вентилей на два-три порядка. Если это правда, это может позволить гораздо меньшим квантовым компьютерам взломать шифрование RSA.

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

Но у идеи уже появились и критики. Например, Мартин Экеро, исследователь квантовых вычислений шведского правительства, говорит, что алгоритму Регева, похоже, нужна квантовая память для хранения промежуточных значений. Обеспечение такой памяти потребует дополнительных кубитов и съест все имеющиеся у нее вычислительные преимущества.

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

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