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

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

Оглавление

• Введение

• Часть 1. Настоящее
  

  • Почему постквантовая эпоха может и не наступить (как минимум в обозримом будущем)

  • Безопасность существующих криптографических алгоритмов

• Часть 2. Будущее
  

  • Требования, накладываемые на постквантовый блокчейн

  • Алгоритмы обхода постквантовых атак
    

    • Постквантовые алгоритмы шифрования

    • Постквантовые алгоритмы подписи

• Заключение 

Введение

Безопасность блокчейна основана на двух вычислительно сложных задачах: поиске коллизий хеша и взятии дискретного логарифма или же факторизации больших чисел. И если на классическом компьютере они могут быть решены не быстрее, чем за экспоненциальное или субэкспоненциальное время (т.е. выбор длинного ключа или криптографически стойкой хеш-функции делает задачу нерешаемой за адекватное время), то квантовый компьютер сможет их решать на порядки эффективнее за счет алгоритмов Шора (разложения числа на простые множители), Гровера (решение задачи перебора, быстрый поиск в неупорядоченной базе данных) и Дойча-Йожи (ответ на вопрос, постоянная или сбалансированная функция). Уязвимы станут самые популярные алгоритмы, включая RSA (основан на факторизации больших целых чисел), ECDSA (алгоритм цифровой подписи над группой точек эллиптической кривой), ECDH (алгоритм Диффи-Хеллмана на эллиптических кривых) или DSA (алгоритм создания цифровой подписи, основанный на дискретном логарифмировании).

WARNING: да, это лонгрид (и мне не стыдно)

Я старалась преподнести тему последовательно, хотя бы касаясь всех этапов рассмотрения этой темы, чтобы у читателя сложилось понимание того, почему, как и что с этим делать. Обрывочных сведений на просторах интернета и так полно)) Получилось или нет, судить уже вам.

ЧАСТЬ 1. Настоящее

Почему постквантовая эпоха может и не наступить (как минимум в обозримом будущем)

Как бы ни была заманчива идея изобретения вычислительной техники, заметно превосходящей нынешнюю в мощности и быстродействии, на пути создания квантового компьютера существует множество проблем. Осуществление квантовой операции состоит из нескольких логических глав: приведение кубитов (аналогов “нулей и единиц” в современных компьютерах) в определенные исходные состояния, объединение их в запутанные системы, изолирование этих систем от влияния внешних помех, считывание результатов квантового расчета. И каждая из них имеет свои сложности, связанные с преодолением естественных для такой системы препятствий для получения результата с требуемой точностью.

Одной из таких проблем является сложность производства однородных и стабильных кубитов. Квантовый компьютер работает на вероятностном принципе, результатом работы является распределение вероятностей возможных ответов, и наиболее вероятный ответ обычно является лучшим решением. А потому, для того, чтобы избежать случайной потери данных, необходимо полностью исключить возможность воздействия случайного постороннего шума и любого наблюдения за системой (it’s how quantum mechanics works). Поэтому для устойчивой работы системы кубитов необходимо поддерживать температуру окружающей среды около 20 мК, что сложно достижимо даже в лабораторных условиях. Ученые используют сверхтекучие жидкости, чтобы добиться такого охлаждения. На данный момент, ученые Университета Дьюка в США заявили, что смогли создать более устойчивые к помехам квантовые системы, чем существовали до сих пор. Разработчикам удалось успешно перевести кубит в начальное состояние в 99,4% случаев при ожидаемой цифре в 98,9%.

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

Безопасность существующих криптографических алгоритмов

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

Прежде всего следует отметить, что стойкость криптосистем с открытым ключом к классическим компьютерным атакам традиционно оценивается с помощью так называемого уровня безопасности битов (англ. bits-of-security level). Такой уровень определяется как усилие, необходимое классическому компьютеру для выполнения атаки методом грубой силы (англ. brute-force attack), по сути, методом перебора всех возможных комбинаций. Например, асимметричная криптосистема имеет 1024-битную защиту, когда усилия, необходимые для ее атаки с помощью классического компьютера, аналогичны усилиям, необходимым для проведения атаки грубой силы на 1024-битный криптографический ключ. Для справки в таблице 1 указан уровень безопасности некоторых из самых популярных симметричных и асимметричных криптосистем.

Стоимость взлома современных 80-битных криптосистем на классических компьютерах оценивается от десятков тысяч до сотен миллионов долларов. В случае 112-битных криптосистем они считаются безопасными для классических компьютерных атак в течение следующих 30-40 лет. Однако исследователи определили, что 160-битные эллиптические кривые можно взломать с помощью 1000-кубитного квантового компьютера, а для 1024-битного RSA потребуется примерно 2000 кубитов. Такая угроза затрагивает криптосистемы, которые полагаются на целочисленную факторизацию (например, RSA), эллиптические кривые (например, ECDSA, ECDH), и основанные, например, на задаче дискретного логарифмирования в поле вычетов по модулю простого числа, которые можно быстро решить с помощью квантового алгоритма Шора.

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

ЧАСТЬ 2. Будущее

Требования, накладываемые на постквантовый блокчейн

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

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

2. Маленькая подпись и длина хеша. Блокчейн хранит транзакции данных, включая подписи пользователей и хеши данных / блоков. Следовательно, если длина подписи / хеша увеличивается, размер блокчейна также увеличивается.

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

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

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

Алгоритмы обхода постквантовых атак 

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

Спойлер: идеального алгоритма, удовлетворяющего всем вышеперечисленным критериям пока не найдено... Но проводятся активные исследования!

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

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

Постквантовые алгоритмы шифрования

1) Code-Based криптосистемы

В таких системах создание закрытого ключа базируется на коде, исправляющим ошибки. К примеру, рассмотрим систему McEliece, безопасность которой основана на NP-сложности декодирования полных линейных кодов. Такая схема обеспечивает быстрое шифрование и относительно быстрое дешифрование, что является преимуществом при выполнении быстрых транзакций блокчейна. Однако криптосистема McEliece требует хранения и выполнения операций с большими матрицами, которые действуют как открытые и закрытые ключи. Такие матрицы обычно занимают от 100 килобайт до нескольких мегабайт, что накладывает ограничения на используемую технику. Для решения этой проблемы используются методы сжатия матриц, а также использование кодов, таких как LDPC (англ. Low Density Parity Check).

2) Multivariate-Based криптосистемы

Схемы на основе многих переменных (также известные как многомерная криптография) основаны на сложности решения систем квадратичных многочленов с несколькими переменными, которые, являются NP-сложными или NP-полными.

В настоящее время некоторые из наиболее многообещающих многомерных схем основаны на использовании квадратных матриц со случайными квадратичными многочленами: криптосистемы, полученные из алгоритма Мацумото-Имаи (англ. Matsumoto-Imai), и схемы, основанных на уравнениях скрытого поля (англ. Hidden Field Equations - HFE).

3) Lattice-Based криптосистемы

Этот вид криптографических схем основан на решетках, которые представляют собой наборы точек в N-мерных пространствах с периодической структурой. Схемы безопасности на основе решеток полагаются на предполагаемую сложность таких задач, как поиск самого короткого вектора (англ. Shortest Vector Problem - SVP), которая является NP-сложной задачей, ее цель - найти кратчайший ненулевой вектор в решетке. Существуют и другие подобные задачи, связанные с решеткой, такие как проблема поиска ближайшего вектора (англ. Closest Vector Problem - CVP) или проблема поиска кратчайших независимых векторов (англ. Shortest Independent Vectors Problem - SIVP), которые в настоящее время не могут быть эффективно решены с помощью квантовых компьютеров.

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

4) Supersingular Elliptic Curve Isogeny криптосистемы 

Эти схемы основаны на протоколе суперсингулярных изогений для обычных эллиптических кривых. Примером является наиболее многообещающая схема шифрования для замены алгоритмов на самих эллиптических кривых: SIKE . SIKE основан на псевдослучайных блужданиях в суперсингулярных графах изогении. Хорошим эталоном размеров ключей SIKE является SIKEp434, который для 128-битного уровня классической безопасности использует 2640-битный открытый ключ и 2992-битный закрытый ключ.

Если вас (как и меня) ужасает словосочетание «суперсингулярные изогении», то вот тут бравый хабровчанин подробно описал что это и с чем его едят - советую прочесть!

5) Гибридные криптосистемы

Гибридные схемы кажутся следующим шагом на пути к постквантовой безопасности, поскольку они объединяют доквантовые и постквантовые криптосистемы с целью защиты передаваемых данных как от квантовых атак, так и от атак на используемые постквантовые схемы. Вторая версия гибридной схемы (англ. Combined Elliptic-Curve and Post-Quantum 2 - CECPQ2) предназначена для усиления криптографической защиты вокруг TLS-соединений. Благодаря этому алгоритму будет невозможным расшифровать HTTPS-трафик и получить доступ к прошлым безопасным коммуникациям.

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

Постквантовые алгоритмы подписи

1) Code-Based криптосистемы

В прошлом подразделе уже говорилось о code-based системах. Для решения проблем именно с постквантовыми подписями, используются усовершенствованные алгоритмы на основе рассмотренного McEliece, например Niederreiter и CFS (от фамилий Courtois, Finiasz, Sendrier). Подписи, созданные по таким схемам имеют небольшую длину и могут быть проверены очень быстро, но, как это и в классическом McEliece, использование ключей большого размера требует значительных вычислительных ресурсов, из-за чего генерация подписи может стать неэффективной.

2) Multivariate-Based криптосистемы

Рассмотренные выше схемы на основе алгоритма Мацумото-Имаи или на HFE помогают и в генерации подписей. Благодаря им можно создавать подписи с размером, сопоставимым с используемыми в настоящее время RSA. Тем не менее, такие криптосистемы нуждаются в дальнейшем улучшении, поскольку они требуют нескольких десятков тысяч байтов на ключ.

3) Lattice-Based криптосистемы

Схемы подписей на основе решеток примечательны тем, что требуют ключей, размер которых меньше размера, необходимого для схем на основе многих переменных, но при этом сгенерированные подписи получаются немного больше. Как пример данного типа алгоритмов, можно привести BLISS-B (Bimodal Lattice Signatures B), созданный на основе решения задачи кратного целочисленного решения (англ. Short Integer Solution - SIS). Однако BLISS-B подвержен атакам на кэш, которые могут восстановить секретный ключ подписи после 6000 генерации подписи. Намного более интересен для рассмотрения алгоритм FALCON, который тоже основан на проблеме SIS. Он использует самые маленькие размеры ключей среди решеточных алгоритмов и обладает высокой скоростью обработки операций.

4) Supersingular Elliptic Curve Isogeny криптосистемы

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

5) Hash-Based схемы

Безопасность таких схем зависит не от сложности математической задачи, а от безопасности лежащей в основе хеш-функции. Подобные схемы появились еще в конце 70-х годов, когда была предложена схема подписи, основанная на односторонней функции. В настоящее время варианты расширенной схемы подписи Меркла (англ. eXtended Merkle Signature Scheme - XMSS), основанные на схеме дерева Меркла, считаются наиболее многообещающими схемами подписи в этом классе.

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

Заключение

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

Пусть на данный момент мы может говорить лишь о претендентах на роль “спасителя”, которые с той или иной вероятностью станут в будущем так же привычны, как и, например, RSA сейчас. Но лично я уверена, что внезависимости от скорости внедрения квантовых компьютеров, разработки в этой сфере являются хорошим подспорьем для самых разных достижений и открытий. Да и криптографы могут решить перестраховаться чуть заранее и обезопасить блокчейн пускай даже от только надвигающейся угрозы, “вдруг что”. Технология-то хорошая, перспективная… Так что можете с чистой совестью оставить свои крипто-накопления и бабулин матрас в покое (хотя бы на ближайшие лет 10). 

Благодарю за прочтение данного лонгрида, надеюсь, моя статья была полезна для вас!

Литература:

• T. M. Fernández-Caramès and P. Fraga-Lamas, "Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks"

• D. Aggarwal, G. K. Brennen, T. Lee, M. Santha and M. Tomamichel "Quantum attacks on Bitcoin, and how to protect against them"

• J. Proos and C. Zalka, "Shor’s discrete logarithm quantum algorithm for elliptic curves", Quantum Inf. Comput., vol. 3, no. 4, pp. 317-344, 2003

• National Institute of Standards and Technology Interagency or Internal Report 8309 39 pages (July 2020)