Опираясь на знаковый алгоритм, исследователи предлагают способ создания меньшей по размеру и более помехоустойчивой квантовой факторной схемы для криптографии.
Самое последнее электронное письмо, которое вы отправили, скорее всего, было зашифровано с помощью проверенного метода, который основан на идее, что даже самый быстрый компьютер не сможет эффективно разбить гигантское число на множители.
Квантовые компьютеры, с другой стороны, обещают быстро взламывать сложные криптографические системы, которые классический компьютер никогда не сможет разгадать. Это обещание основано на алгоритме квантового факторинга, предложенном в 1994 году Питером Шором, который в настоящее время является профессором Массачусетского технологического института.
Но в то время как за последние 30 лет исследователи добились больших успехов, ученым еще предстоит создать квантовый компьютер, достаточно мощный для выполнения алгоритма Шора.
В то время как некоторые исследователи работают над созданием более крупных квантовых компьютеров, другие пытаются усовершенствовать алгоритм Шора, чтобы он мог работать на меньшей квантовой схеме. Около года назад специалист по информатике из Нью-Йоркского университета Одед Регев предложил серьезное теоретическое усовершенствование. Его алгоритм мог бы работать быстрее, но схема потребовала бы больше памяти.
Основываясь на этих результатах, исследователи из Массачусетского технологического института предложили подход «лучший из двух миров», который сочетает в себе скорость алгоритма Regev с эффективностью памяти Шора. Этот новый алгоритм такой же быстрый, как и алгоритм Regev, требует меньшего количества квантовых строительных блоков, известных как кубиты, и имеет более высокую устойчивость к квантовому шуму, что может сделать его более осуществимым для реализации на практике.
В долгосрочной перспективе этот новый алгоритм может послужить основой для разработки новых методов шифрования, которые смогут противостоять взлому кода квантовых компьютеров.
«Если когда-нибудь будут построены крупномасштабные квантовые компьютеры, то факторинг станет проблемой, и нам придется найти что-то еще, что можно использовать для криптографии. Но насколько реальна эта угроза? Можем ли мы сделать квантовый факторинг практичным? Наша работа потенциально может приблизить нас на один шаг к практической реализации», — говорит Винод Вайкунтанатан, профессор инженерии Фонда Форда, член Лаборатории компьютерных наук и искусственного интеллекта (CSAIL) и старший автор статьи, описывающей алгоритм.
Ведущим автором статьи является Сеюн Рагаван, аспирант кафедры электротехники и компьютерных наук Массачусетского технологического института. Исследование будет представлено на Международной конференции по криптологии 2024 года.
Взлом криптографии
Для безопасной передачи сообщений через Интернет поставщики услуг, такие как почтовые клиенты и приложения для обмена сообщениями, обычно полагаются на RSA, схему шифрования, изобретенную исследователями Массачусетского технологического института Роном Ривестом, Ади Шамиром и Леонардом Адлеманом в 1970-х годах (отсюда и название «RSA»). Система основана на идее, что разложение на множители 2048-битного целого числа (числа, состоящего из 617 цифр) слишком сложно для компьютера за разумное время.
Эта идея была перевернута с ног на голову в 1994 году, когда Шор, работавший тогда в Bell Labs, представил алгоритм, который доказал, что квантовый компьютер может достаточно быстро разложить множители, чтобы взломать криптографию RSA.
«Это был поворотный момент. Но в 1994 году никто не знал, как построить достаточно большой квантовый компьютер. И мы все еще довольно далеки от этого. Некоторые люди задаются вопросом, будут ли они когда-нибудь построены», — говорит Вайкунтанатан.
Подсчитано, что квантовому компьютеру потребуется около 20 миллионов кубитов для запуска алгоритма Шора. В настоящее время крупнейшие квантовые компьютеры имеют около 1100 кубитов.
Кубит ― это аналог классического носителя информации, известного как обычный бит в компьютерах. Это (классический бит) некая логическая единица, которая может принимать два значения, скажем: ноль и единичка. Их можно реализовывать при помощи транзисторов, которые могут переключаться между состояниями с разным напряжением ― разному уровню напряжения можно присвоить значения ноль и единичка. Так работает обычный компьютер.
Квантовый компьютер выполняет вычисления с использованием квантовых схем, точно так же, как классический компьютер использует классические схемы. Каждая квантовая схема состоит из ряда операций, известных как квантовые вентили. Эти квантовые вентили используют кубиты, которые являются самыми маленькими строительными блоками квантового компьютера, для выполнения вычислений.
Но квантовые вентили вносят шум, поэтому меньшее количество вентилей улучшит производительность машины. Исследователи стремились усовершенствовать алгоритм Шора, чтобы его можно было запустить на меньшей схеме с меньшим количеством квантовых вентилей.
Именно это Регев сделал с схемой, которую он предложил год назад.
«Это была большая новость, потому что это было первое реальное улучшение трассы Шора с 1994 года», — говорит Вайкунтанатхан.
Квантовая схема, предложенная Шором, имеет размер, пропорциональный квадрату разлагаемого числа. Это означает, что если бы кто-то разложил на множители 2048-битное целое число, схеме потребовались бы миллионы вентилей.
Схема Regev требует значительно меньшего количества квантовых вентилей, но ей требуется гораздо больше кубитов, чтобы обеспечить достаточную память. Это создает новую проблему.
«В каком-то смысле некоторые виды кубитов похожи на яблоки или апельсины. Если вы держите их рядом, они со временем разрушаются. Вы хотите свести к минимуму количество кубитов, которые нужно держать при себе», — объясняет Вайкунтанатан.
Он слышал, как Регев рассказывал о своих результатах на семинаре в августе прошлого года. В конце своего выступления Регев задал вопрос: может ли кто-нибудь улучшить его схему, чтобы она нуждалась в меньшем количестве кубитов? Вайкунтанатхан и Рагаван подхватили этот вопрос.
Квантовый пинг-понг
Чтобы разложить на множители очень большое число, квантовая схема должна быть запущена много раз, выполняя операции, требующие вычислительных мощностей, таких как 2 в степени 100.
Но вычисления таких больших мощностей на квантовом компьютере стоят дорого и сложны, поскольку квантовые компьютеры могут выполнять только обратимые операции. Возведение числа в квадрат не является обратимой операцией, поэтому каждый раз, когда число возводится в квадрат, необходимо добавить больше квантовой памяти для вычисления следующего квадрата.
Исследователи из Массачусетского технологического института нашли умный способ вычисления экспонент с использованием ряда чисел Фибоначчи, который требует простого умножения, которое является обратимым, а не возведения в квадрат. Их метод требует всего двух блоков квантовой памяти для вычисления любой экспоненты.
«Это похоже на игру в пинг-понг, где мы начинаем с числа, а затем прыгаем вперед и назад, умножая между двумя квантовыми регистрами памяти», — добавляет Вайкунтанатан.
Они также решили проблему исправления ошибок. Схемы, предложенные Шором и Регевом, требуют, чтобы каждая квантовая операция была корректной для работы их алгоритма, говорит Вайкунтанатхан. Но безошибочные квантовые вентили были бы невозможны на реальной машине.
Они преодолели эту проблему, используя технику, позволяющую отфильтровывать поврежденные результаты и обрабатывать только правильные.
Конечным результатом является схема, которая значительно более эффективно использует память. Кроме того, их метод исправления ошибок сделал бы алгоритм более практичным для развертывания.
«Авторы устраняют два наиболее важных места в более раннем алгоритме квантового факторинга. Несмотря на то, что их работа все еще не сразу срабатывает, они приближают алгоритмы квантового факторинга к реальности», — добавляет Регев.
В будущем исследователи надеются сделать свой алгоритм еще более эффективным и когда-нибудь использовать его для тестирования факторинга на реальной квантовой схеме.
«Главный вопрос после этой работы: действительно ли это приближает нас к взлому криптографии RSA? Пока это не ясно; В настоящее время эти усовершенствования вступают в силу только тогда, когда целые числа намного больше 2048 бит. Можем ли мы продвинуть этот алгоритм и сделать его более осуществимым, чем алгоритм Шора, даже для 2048-битных целых чисел?» — говорит Рагаван.
Эта работа финансируется президентской стипендией Akamai, Агентством перспективных оборонных исследовательских проектов США, Национальным научным фондом, лабораторией искусственного интеллекта Watson MIT-IBM, стипендией Thornton Family Faculty Research Innovation Fellowship и премией Simons Investigator Award.