В последние годы академические круги, промышленность и правительство инвестировали энергию и ресурсы в область квантовых вычислений, в компьютеры, которые используют явления квантовой механики для решения математических задач, которые являются сложными или непрактичными для обычных компьютеров.
Если когда-нибудь начнется крупномасштабное производство квантовых компьютеров, они смогут взломать многие из используемых в настоящее время криптографических систем с открытым ключом (или асимметричных). Это серьезно подорвет конфиденциальность и целостность цифровых коммуникаций в Интернете и в других местах.
В этом контексте цель криптографии пост-квант (o квантово-сейф) заключается в разработке шифров, безопасных как от атак криптоанализа, проводимых с помощью квантовых компьютеров, так и классических, и которые могут одновременно взаимодействовать с существующими протоколами связи и сетями.
В то время как криптография с открытым ключом, шифрование с двойным ключом для шифрования / дешифрования может оказаться под серьезной угрозой из-за появления квантовых компьютеров, симметричная (или частная) криптография и хэш-функции основаны на проблемах, устойчивых квантовые алгоритмы. Среди них наибольшую угрозу симметричным шифрам представляютАлгоритм Гровера (задумано Lov Grover в 1996 году в Bell Labs1). Этот алгоритм, работающий на квантовом компьютере, позволяет вам искать элемент в неупорядоченном списке длины N за время, пропорциональное квадратному корню из N. Напротив, на классическом компьютере время будет пропорционально N Это означает, что для получения того же уровня безопасности длина ключа должна быть увеличена вдвое.
Среди алгоритмов симметричного ключаШифрования Advanced Encryption Standard (AES), Blowfish, то Twofish или змий, с длиной ключа больше или равной 256 бит и при соответствующих условиях они могут проявить себя квантово-сейф.
Однако в области асимметричной криптографии перспектива менее обнадеживающая. Криптосистемы с открытым ключом в основном используются для выполнения двух основных задач: безопасного обмена ключами, их последующего использования с симметричными шифрами и цифровой подписи.
Наиболее известные и используемые в настоящее время шифры с открытым ключом включают в себя:
- RSA, основанная на проблеме факторизации целых чисел;
- криптография на основе эллиптических кривых, которая основывает свою безопасность на сложности выполнения определенных операций на точках кривой этого типа;
- Диффи-Хеллман обратил внимание на сложность вычисления дискретного логарифма для некоторых циклических групп.
Для каждого из них можно легко провести атаку криптоанализа, расшифровывая информацию без использования ключа, с помощьюАлгоритм Шора (задумано Петром Шором в 1994 г.2), работающий на квантовом компьютере. Причина, по которой алгоритм Шора способен «взламывать» криптографические системы с открытым ключом, является следствием того факта, что они основаны на задачах с неполиномиальной вычислительной сложностью, которые могут быть решены квантовым компьютером за полиномиальное время. В частности, для заданного целого числа N алгоритм Шора факторизует его за полиномиальное время в журнал (N), в то время как на классическом компьютере время экспоненциально в N.
Мотивированный этими соображениями, американский Национальный Институт Стандартов и Технологий (NIST) предпринял выбор криптографических алгоритмов с открытым ключом квантово-сейф в конце публичного звонка, объявленного на конференции PQCrypto в 2016 году и запущенного в декабре того же года.
В приглашении было собрано 82 кандидатных алгоритма, которые с помощью процессов коллегиального обзора и раундов отбора сузили их до завершения, предположительно к 2024 году, с выпуском стандарта.
Новые шифры будут приняты Соединенными Штатами по аналогии с предыдущими инициативами по внедрению Стандарт шифрования данных (DES) и AES.
Между классами алгоритмов пост-квант наиболее перспективными являются алгоритмы, основанные на «криптографии на основе кода», которая была введена в 1978 году американцем Робертом МакЭлисом3 для криптографии с открытым ключом им не повезло из-за чрезмерного размера ключа. Тем не менее, сегодня существуют варианты, способные предложить значительно уменьшенные и конкурентоспособные размеры ключей. Эти алгоритмы основаны на сложности поиска в огромном неупорядоченном наборе чисел. Также было теоретически доказано, что они принадлежат к классу так называемых NP (недетерминированных полиномов) задач, которые могут противостоять квантовым вычислениям.
Второй класс, Многомерная криптография4, основывается на сложности решения систем квадратичных алгебраических уравнений от многих переменных (NP-твердость).
Третий класс основан на алгебраической концепции «решетки» (Латексная криптография), включая варианты, основанные на проблеме «обучения с ошибками», которая заключается в восстановлении функции по некоторым ее неточным оценкам5. Эта формулировка позволила определить некоторые инновационные алгоритмы асимметричной криптографии, сопровождаемые серьезными демонстрациями безопасности.
Внедрение новых шифров с открытым ключом квантово-сейф сегодня представляет собой неизбежное усилие. Повсеместное использование текущих алгоритмов открытых ключей влияет на повседневную жизнь каждого, от безопасного просмотра в Интернете до банковских систем безопасности, от цифровых подписей до криптовалют.
Для одних это гонка со временем, тогда как для других потребуется время, чтобы вычислительная мощность квантового компьютера достигла уровня, необходимого для того, чтобы сделать существующие стандарты устаревшими.
Тем временем, однако, в частном секторе гиганты, такие как Google и IBM, проводят эксперименты, направленные на достижение так называемого «квантового превосходства», бросая вызов друг другу в достижении новых и все более амбициозных результатов вычислений. Кроме того, с той же целью в международной сфере такие сверхдержавы, как Соединенные Штаты и Китай, а также Европейский союз, вкладывают все большие средства в разработку планов исследований в области квантовые вычисления. Китай, например, недавно объявил о своем намерении построить к 2020 году национальную лабораторию квантовой информации в Хэфэе, для которой будет выделен многолетний бюджет в размере десяти миллиардов долларов.6.
В то же время в европейском контексте новый президент Европейской комиссии Урсула фон дер Лейен высказался по этому вопросу, заявив, что квантовые вычисления является одним из приоритетов Союза и выражает желание поддержать инициативы в области развития в этой области, а также делает европейские вычислительные ресурсы доступными для научных кругов и научных исследований посредством облако. С этой целью Союз выделил миллиард долларов для использования в течение следующих десяти лет.7, для разработки определенных проектов уже определены.
В этом контексте причина спазматической «расы» государственных и частных субъектов, направленная на достижение вышеупомянутого превосходства в области квантовые вычисления, находится в словах, что Майк Маккол8Североамериканский политик и член Американского института предпринимательства в 2018 году выступил с речью о конкуренции в области квантовые вычисления США с такими глобальными противниками, как Китай, Россия, Северная Корея и Иран: «Я верю, что любая сверхдержава, достигшая этой цели раньше других, оснастится первой цифровой ядерной бомбой».
1 Гровер, «Быстрый квантово-механический алгоритм для поиска в базе данных», Труды, 28-й ежегодный симпозиум ACM по теории вычислений, с. 212, 1996.
2 Шор, «Алгоритмы квантовых вычислений: дискретный лог и факторинг», в материалах 35-го ежегодного симпозиума по основам информатики, Санта-Фе, IEEE Computer Society Press, стр. 124-134, 1994.
3 МакЭлис, «Система открытых ключей, основанная на теории алгебраического кодирования», Отчет о проделанной работе DSN 44, стр. 114-116, 1978.
4 Мацумото, Имаи, «Класс асимметричных криптосистем, основанных на многочленах над конечными кольцами», IEEE Международный симпозиум по информационной теории, Автореферат статей, с. 131-132, 1983.
5 Гольдрайх, Гольдвассер, Халеви, «Криптосистема с открытым ключом из задачи сокращения решетки», в Proc. Of Crypto '97, том 1294 LNCS, стр. 112-131, IACR, Springer-Verlag, 1997.
6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon
7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...
8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...
Фото: IBM
