Аннотация
Мы объясняем принцип работы подписей Лэмпорта — схемы квантово-безопасной цифровой подписи, основанной на хэшировании, разработанной в 1979 году. Мы используем их, чтобы проиллюстрировать, как квантово-безопасные подписи могут быть очень простыми и не требовать сложных математических вычислений. Мы утверждаем, что подписи на основе хэшей могут стать решением, если Bitcoin примет схему квантово-безопасной подписи.
Введение
Сейчас тема подверженности Bitcoin квантовым рискам является горячей темой. Недавно в Сан-Франциско прошла конференция Presidio Bitcoin, посвящённая этому вопросу. Мы считаем, что нужно стараться быть максимально рациональными. Мы не понимаем квантовые вычисления и не видели, чтобы квантовое оборудование достигло чего-то особенно впечатляющего, поэтому, вероятно, волноваться пока не стоит. Однако мы понимаем, что идея квантовых вычислений пугает некоторых, и развитие квантовых технологий теоретически может произойти неожиданно быстро.
Одна из общих проблем заключается в том, что Bitcoin может потребоваться обновление до новой, сложной и рискованной постквантовой криптографической схемы цифровой подписи. Существует множество новых схем, о которых можно прочитать, в том числе HAWK, SQI, Falcon и CRYSTALS. Однако у новых схем могут быть риски: что, если мы выберем неправильную схему? В 2023 году появились сообщения о том, что новая постквантовая схема — алгоритм SIKE — была взломана классическими, не квантовыми средствами. И что, если квантовые вычисления будут быстро развиваться?
Как работают подписи Лэмпорта
В этом примере мы предполагаем, что в подписях Лэмпорта используется алгоритм хэширования SHA256, однако схема может работать практически с любым алгоритмом хэширования.
С подписями Лэмпорта закрытый ключ — это не одно случайное 256-битное число, как в случае с ECDSA, а два набора из 256 случайных чисел по 256 бит. В нашем примере это наборы A и B. Таким образом, закрытый ключ составляет 131 072 бита = 16,3 КБ. Каждый из этих 512 случайных чисел длиной 256 бит затем хэшируется, и выходные хэши являются открытым ключом, поэтому открытый ключ также составляет 16,3 КБ.
Адрес Bitcoin может быть хэш-кодом SHA256 конкатенации всех строк, составляющих открытый ключ.
Подписание сообщения
Первый шаг для подписания сообщения — это хэширование сообщения с использованием SHA256, и в результате получается строка в двоичном виде. На основе каждой цифры двоичного вывода определяется, какая часть закрытого ключа будет включена в подпись. Значение бита, равное нулю, соответствует набору A, а значение бита, равное единице, — набору B. Первый бит в хэш-выводе соответствует первому числу в закрытом ключе, второй — второму и так далее. Таким образом, подпись состоит из случайного выбора ровно 50 % от общего количества закрытого ключа.
Проверка сообщения
Для проверки сообщения верификатору нужно просто хэшировать сообщение и выбрать соответствующие части открытого ключа, используя ту же методологию. Затем верификатор должен хэшировать каждое число в подписи, чтобы увидеть, соответствуют ли они этим 256 частям открытого ключа. Если есть полное совпадение, подпись действительна.
Недостатки схемы
Ключевым недостатком этой схемы является то, что её можно использовать для каждой подписи только один раз. После того как транзакция подписана в блокчейне, 50 % закрытого ключа публикуются. Если подпись используется снова, то публикуются ещё 50 % ключа. Статистически это означает, что 75 % от общего количества закрытого ключа теперь ожидается публично доступным.
Ещё один недостаток — невозможность выполнения сложных математических операций, как в случае с ECDSA. Например, BIP-32, иерархические детерминированные кошельки, используют характеристики ECDSA для использования «xpubs», что невозможно сделать только с помощью хэшей.
Размер
Ещё один важный момент — это огромный размер подписей и открытых ключей. Подпись составляет 8 КБ, а открытый ключ — 16 КБ, что в сумме составляет 24 КБ. Блок Bitcoin может включать в себя только десятки транзакций, а не тысячи, как сегодня. Однако все квантово-безопасные схемы в той или иной степени имеют эту проблему.
Заключение
Мы не имеем чёткого представления об уровне квантового риска для ECDSA, и у нас нет конкретных данных. Мы считаем, что схема ECDSA, которую использует Bitcoin, будет безопасной в течение многих десятилетий, и рациональный подход может заключаться в том, чтобы ничего не делать, пока у нас не будет более конкретных примеров возможностей квантовых компьютеров. Однако стоит подумать о том, что потребуется для того, чтобы сделать Bitcoin квантово-безопасным. Первый шаг — создание способа тратить Bitcoin квантово-безопасным способом, которым может стать схема подписи на основе хэшей.
Если будет добавлен квантово-безопасный способ тратить Bitcoin, и его использование будет широко распространено, только тогда стоит вступать в подобные дискуссии.
Не является инвестиционной рекомендацией.