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

Квантовые компьютеры могут быстро взломать сложные криптографические системы, которые классический компьютер, возможно, никогда не сможет разгадать. Это основано на алгоритме квантового факторинга, предложенном Питером Шором в 1994 году. Сейчас Шор — профессор Массачусетского технологического института.

Исследователи добились больших успехов за последние 30 лет, но им ещё предстоит создать квантовый компьютер, достаточно мощный для запуска алгоритма Шора.

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

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

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

Профессор Винод Вайкунтанатан из Фонда Форда и старший автор статьи об алгоритме задаётся вопросом:

Насколько реальна эта угроза? Можем ли мы сделать квантовый факторинг практичным?

Исследование будет представлено на Международной криптологической конференции в 2024 году. Его ведущий автор — аспирант Массачусетского технологического института Сейюн Рагаван.

Взлом криптографии

Провайдеры используют схему шифрования RSA для безопасной передачи сообщений через интернет. Её изобрели в 1970-х годах Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (отсюда название «RSA»).

Система основана на том, что компьютеру сложно факторизовать 2048-битное целое число (число с 617 цифрами) за разумное время.

В 1994 году Питер Шор из Bell Labs представил алгоритм, который показал, что квантовый компьютер может быстро факторизовать числа и взломать криптографию RSA.

В 1994 году никто не знал, как построить достаточно большой квантовый компьютер. Мы всё ещё далеки от создания такого устройства. Некоторые сомневаются, что это вообще возможно, — говорит Вайкунтанатан.

Для выполнения алгоритма Шора потребуется около 20 миллионов кубитов. Самые большие квантовые компьютеры сейчас имеют около 1 100 кубитов.

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

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

Регев усовершенствовал предложенную им ранее схему. Это первое реальное улучшение схемы Шора 1994 года, говорит Вайкунтанатан.

В схеме Шора количество вентилей пропорционально квадрату факторизуемого числа. Поэтому для разложения 2048-битного числа нужны миллионы вентилей.

Схема Регева требует меньше квантовых ворот, но больше кубитов для достаточного объёма памяти. Это создаёт проблему.

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

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

Квантовый пинг-понг

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

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

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

Это как игра в пинг-понг: мы начинаем с числа и перемножаем его, перемещая между двумя регистрами квантовой памяти, — добавляет Вайкунтанатан.

Схемы Шора и Регева требуют безошибочности каждой квантовой операции. Но создать квантовые ворота без ошибок на реальной машине невозможно.

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

Авторы устранили два узких места в алгоритме квантовой факторизации. Это приближает алгоритмы к реальности, — отмечает Регев.

В будущем исследователи хотят сделать алгоритм ещё более эффективным и использовать его для тестирования факторизации на реальной квантовой схеме.

Рагаван задаётся вопросом: приблизит ли это нас к взлому криптографии RSA? Пока неясно. Улучшения работают только с числами больше 2048 бит. Сможем ли мы сделать этот алгоритм более реализуемым, чем алгоритм Шора, даже для 2048-битных чисел?