Физик Алексей Федоров о квантовых технологиях, принципе блокчейна и электронно-цифровых подписях.

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

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

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

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

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

Кроме того, в блокчейне есть механизм достижения консенсуса. Одна из его самых интересных особенностей состоит в том, что через него мы можем сформировать некоторый набор информации, которому мы все доверяем. Это основывается на механизме достижения консенсуса, который называется proof of work — доказательство работы. На самом деле в этот механизм тоже заложено решение некоторой сложной математической задачи — он не основан на чем-то действительно фундаментальном. Чтобы все подделать и всех обмануть, нужно обладать очень большим количеством вычислительных ресурсов. Поскольку мы знаем, что эти ресурсы распределены, а не сосредоточены в одних руках, у такой системы есть достаточно высокий уровень надежности. Возможно, это изменится с появлением квантового компьютера, потому что он быстрее решает некоторые классы математических задач, в частности задачи, которые косвенно относятся к задачам о достижении консенсуса.

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

Это породило целую сферу, которая называется постквантовые электронно-цифровые подписи и является довольно большим и бурно развивающимся исследовательским направлением. Национальным институтом стандартов и технологий (NIST) сейчас объявлен конкурс на создание алгоритма для электронно-цифровой подписи. Пока универсального надежного алгоритма для постквантовой электронно-цифровой подписи нет. Тем не менее эта математика, которая активно развивается, представляет большой интерес.

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

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

Возникает другой вопрос: можно ли кроме обеспечения информационно-теоретически стойкого авторства транзакции сделать так, чтобы алгоритм достижения консенсуса между пользователями также не зависел от вычислительных ресурсов? Оказывается, что да. Можно создать алгоритмы широковещания, алгоритмы broadcast. Представим, что у нас есть N пользователей. На первом этапе они посылают друг другу все транзакции, которые хотят добавить в блок. То есть коммуникаций в такой системе изначально достаточно много. На втором этапе каждый из них формирует блок транзакций, который они получили от всех пользователей, и со второго этапа они постоянно обмениваются своими пулами транзакций таким образом, чтобы исключить из них те, которые друг у друга не совпали. Таким образом устраняется возможность добавить в блок транзакцию, которая является ложной или ошибочной. Эта система достаточно известна, она была предложена в 1982 году Лампортом, Пизом и Шостаком. Ее значение в том, что она дает возможность достичь консенсуса между N пользователями, если есть ограничение на количество ошибочных или нечестных пользователей (не больше трети всей сети).

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

Кажется, что в такой системе достаточно много коммуникации. С одной стороны, это правда. С другой стороны, важно отметить, что все зависит не от общего числа пользователей в сети, а от количества пользователей в сети, которые ведут себя нечестно. Если их достаточно мало, то консенсус достигается быстро. Таким образом можно построить информационно-теоретический блокчейн (или информационно-теоретически защищенную базу данных — это сильно зависит от терминологии, от того, что мы на самом деле называем блокчейном), надежность информации в котором гарантируется законами природы: то, что мы не можем подделать авторство, гарантируется квантовой криптографией, а квантовая криптография, в свою очередь, завязана на том, что мы знаем, что законы физики правильно работают. И такая toy model информационно-теоретического блокчейна была протестирована на московской сети квантовых коммуникаций Российским квантовым центром.

Алексей Федоров
PhD in Theoretical Physics Университет Париж-Сакле, старший научный сотрудник Российского Квантового Центра
ПостНаука