Стоит ли Crypto опасаться квантовых вычислений?

Что нужно знать:

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

Квантовые вычисления: следующий большой технологический скачок

Компьютеры, которые мы используем ежедневно, обрабатывают информацию на основе «битов». Бит может содержать только одно из следующих значений: 0 или 1, и может быть соединен вместе для создания фрагмента двоичного кода. Сегодня все, что мы делаем с компьютером, от отправки электронных писем и просмотра видео до обмена музыкой, возможно благодаря таким строкам двоичных цифр. 

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

В 1981 году Ричард Фейнман сказал, что «природа не является классической, и если вы хотите смоделировать природу, вам лучше сделать ее квантово-механической». Вместо того, чтобы манипулировать битами, квантовые вычисления используют «квантовые биты» или кубиты, что позволяет обрабатывать данные гораздо более эффективным способом. Кубиты могут быть нулем, единицей и, самое главное, комбинацией нуля и единицы.

Квантовые вычисления стоят на стыке физики и информатики. Чтобы представить ситуацию в перспективе, квантовому компьютеру на 500 кубитов потребуется больше классических битов, чем… число атомов во всей Вселенной.

Является ли квантовая угроза для криптографии?

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

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

С одной стороны, квантовый алгоритм Шора (1994), названный в честь Питера Шора, позволяет разлагать на множители большие целые числа или решать задачу дискретного логарифмирования за полиномиальное время. Этот алгоритм может взломать криптографию с открытым ключом с помощью достаточно мощного квантового компьютера. Алгоритм Шора сломал бы подавляющее большинство асимметричной криптографии, используемой сегодня, поскольку он основан на RSA (опирающемся на проблему целочисленной факторизации) и криптографии на эллиптических кривых (в зависимости от проблемы дискретного логарифмирования в группе эллиптических кривых). 

С другой стороны, алгоритм Гровера (1996) представляет собой алгоритм квантового поиска, разработанный Ловом Гровером в 1996 году, который можно использовать для решения задач неструктурированного поиска. Алгоритм Гровера значительно снижает безопасность симметричных примитивов, но не является непреодолимым. Обычно рекомендуется удваивать длину ключа, чтобы компенсировать сложность извлечения квадратного корня из этого разрыва. Использование AES256 вместо AES128 считается достаточным, но следует отметить, что это эмпирическое правило может только иногда быть действительным для всех шифров[5]. Что касается хеш-функций, которые являются частью ландшафта симметричных примитивов, считается, что они не влияют на устойчивость к коллизиям. Однако исследователи обнаружили случаи проблемы, когда это неправда[6] (например, многоцелевой поиск прообраза).

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

Когда появятся квантовые компьютеры, взламывающие шифрование?

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

Одним из событий, о котором все, вероятно, слышали, был «эксперимент квантового превосходства» Google в 2019 году с использованием устройства с 54 кубитами. В 2021 году Университет науки и техники Китая решил более сложный расчет с использованием 56 кубитов, достигнув 60 кубитов позже. Его целью было выполнить вычисление без использования алгоритма Шора, которое в равной степени продемонстрировало бы квантовое ускорение по сравнению с классическими вычислениями.

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

Статус разработки квантовых компьютеров BSI [1] показывает, насколько далеки современные квантовые компьютеры от 160-битного дискретного логарифма (самая нижняя синяя линия на следующем изображении). По оси абсцисс показано, как снижение количества ошибок за счет чисто аппаратных усовершенствований или отказоустойчивых вычислений помогает достичь таких уровней вычислений без резкого увеличения количества доступных кубитов (ось Y).

Масштабируемая реализация алгоритма Шора требует отказоустойчивых вычислений на нескольких тысячах логических кубитов: минимум 2124 кубита, чтобы сломать 256-битную эллиптическую кривую, такую ​​как биткойн secp256k1, от Улучшенные квантовые схемы для дискретных логарифмов эллиптических кривых[7]. «Логический» кубит в такой системе состоит из нескольких кубитов, предназначенных для работы в качестве версии одного кубита с исправлением ошибок.

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

Прогресс в этом направлении напрямую выльется в конкретную угрозу криптографии с открытым ключом. Наконец, еще одна возможность для быстрого прогресса может исходить от чисто алгоритмических улучшений или открытий, связанных только с аппаратным обеспечением. Статус разработки квантовых компьютеров BSI[1] объясняет: «Могут быть прорывные открытия, которые резко изменят [текущее состояние знаний], главными из которых являются криптографические алгоритмы, которые могут быть запущены на машинах без исправления ошибок в краткосрочной перспективе, или резкие прорывы в частоте ошибок. некоторых платформ». Другими словами, это не только проблема создания больших компьютеров с большим количеством кубитов (на самом деле надежное создание большего количества кубитов не является основным направлением деятельности, а отказоустойчивые вычисления), но также проблема алгоритмов и, возможно, исследования материалов. один.

Когда мы писали эту статью, IBM опубликовала свои результаты по 127-кубитному чипу с коэффициентом ошибок 0.001 и планирует выпустить 433-кубитный чип в следующем году и 1121-кубитный чип в 2023 году. 

В общем, пока сложно предсказать, как быстро появится квантовый компьютер. Тем не менее, мы можем положиться на мнение экспертов по этому вопросу: Структура оценки ресурсов для квантовых атак на криптографические функции — последние разработки[3] и Экспертный опрос о квантовом риске[4] показывают, что многие эксперты согласны с тем, что через 15–20 лет у нас должен быть доступен квантовый компьютер.

квотирование Структура оценки ресурсов для квантовых атак на криптографические функции — последние разработки [3] в качестве резюме:

«Развернутые в настоящее время схемы с открытым ключом, такие как RSA и ECC, полностью нарушены алгоритмом Шора. Напротив, параметры безопасности симметричных методов и хеш-функций снижаются не более чем в два раза известными атаками — поиском «грубой силой» с использованием поискового алгоритма Гровера. Все эти алгоритмы требуют крупномасштабных отказоустойчивых квантовых машин, которых пока нет. Большинство экспертного сообщества согласны с тем, что они, скорее всего, станут реальностью в течение 10–20 лет».

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

Quantum: какие риски для криптовалют?

Биткойн-кейс:

Давайте начнем с анализа проблемы Биткойна, проведенного Питером Вуйлем, который иногда считается «квантово-безопасным» из-за того, что адреса хэши открытых ключей и, таким образом, не раскрывая их.

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

Ссылаясь на другую ветку, Питер Вуилле дает представление о последствиях кражи ~ 37% открытых средств (на тот момент). Биткойн, вероятно, рухнет, и даже не разоблаченный, все остальные тоже проиграют.

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

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

Случай Эфириума:

Случай Ethereum интересен тем, что ETH 2.0 включает запасной план на случай катастрофического сбоя в EIP-2333.

В случае нарушения подписи BLS ETH2, что произойдет одновременно с ECDSA, поскольку они оба одинаково уязвимы перед лицом алгоритма Шора, будет выполнен хард-форк блокчейна до того, как возникнет подозрение, что алгоритм скомпрометирован. Затем пользователи раскрывают прообраз своего ключа, которым могут владеть только законные владельцы. Сюда не входят ключи, полученные путем взлома подписи BLS. С помощью этого прообраза они подписывают конкретную транзакцию, позволяющую им перейти к хардфорку и использовать новые постквантовые алгоритмы.

Это еще не переход к постквантовой цепочке, но это обеспечивает выход. Еще немного информации здесь.

Постквантовые подписи:

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

Имя кандидата	Размер
радуга	58.3 XNUMX
Дилитий	3.5 XNUMX
Cокол	1.5 XNUMX
ГеМСС	352 XNUMX
Пикник	12 XNUMX
SPHINCS +	7 XNUMX

Алгоритм Falcon был разработан для минимизации размера открытого ключа и подписи. Однако его 1563 байта все еще далеки от 65 байтов, которых в настоящее время достигает ECDSA.

Криптографические методы могут уменьшить размер блока, например, объединение нескольких подписей вместе. Эта [схема мультиподписи](https://eprint.iacr.org/2020/520) для подписи GeMSS делает именно это и снижает стоимость хранения одной подписи до чего-то приемлемого, несмотря на огромную единовременную плату за подпись GeMSS. .

Угрозы криптографическому оборудованию:

Размер подписи также влияет на аппаратные кошельки, где память сильно ограничена: Ledger Nano S имеет 320 КБ доступной флэш-памяти и только 10 КБ оперативной памяти. Если бы нам вдруг понадобилось использовать подписи Rainbow, сгенерировать открытый ключ нативным способом было бы невозможно.

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

Последствия этих перерывов — крах нынешней банковской системы, телекоммуникаций и систем идентификации, таких как паспорта. Что делать перед лицом такого апокалиптического будущего? Не бойтесь, или немного, поскольку криптографы прикрыли это.

Есть ли лекарство, доктор?

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

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

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

В основу этого исследования положены предупреждения экспертов о том, что зашифрованные данные уже могут быть скомпрометированы, поскольку ожидается, что первые практические квантовые компьютеры появятся в ближайшие 15 лет.
Этот тип атаки известен как «сохранить данные сейчас, атаковать позже», когда крупная организация хранит зашифрованную информацию от других сторон, которую она хочет взломать, и ждет, пока достаточно мощный квантовый компьютер позволит ей это сделать. Это то же самое беспокойство, что и эта статья, например, «США обеспокоены тем, что хакеры воруют данные сегодня, чтобы квантовые компьютеры могли взломать их через десятилетие.", но в нем не говорится, что могут делать в том же духе субъекты на государственном уровне. У них гораздо больше ресурсов и памяти.

Заключительные мысли

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

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

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

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

Рекомендации:

[1]: Статус разработки квантовых компьютеров BSI

[2]: Отказоустойчивое управление кубитом с исправлением ошибок

[3]: Структура оценки ресурсов для квантовых атак на криптографические функции — последние разработки

[4]: Экспертный опрос о квантовом риске

[5]: Помимо квадратичного ускорения в квантовых атаках на симметричные схемы

[6]: Эффективный алгоритм поиска квантовых столкновений и последствия для симметричной криптографии

[7]: Улучшенные квантовые схемы для дискретных логарифмов эллиптических кривых

• SEO-контент и PR-распределение. Получите усиление сегодня.
• Платоблокчейн. Интеллект метавселенной Web3. Расширение знаний. Доступ здесь.
• Источник: https://www.ledger.com/blog/should-crypto-fear-quantum-computing