Игорь Голдовский: квантовые компьютеры представляют угрозу для Bitcoin

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

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

Однако для того, чтобы скомпрометировать, например, алгоритм цифровой подписи ECDSA на кривой P-256 требуется квантовый компьютер с примерно 1500 тысячами чистых логических кубитов, что в пересчете на физические кубиты составляет 15-20 млн кубитов. Сегодня существуют квантовые компьютеры с 5000 физическими кубитами. Ожидается, что компьютеры с таким числом кубитов появятся в 2035-2040 гг.

Чтобы справиться с проблемой компрометации современных алгоритмов подписи на квантовых компьютерах, институт NIST провел конкурс и даже стандартизировал новые алгоритмы цифровой подписи. К ним относится алгоритм CRYSTALS-Dilithium (ML-DSA), основанный на решении NP-трудной задачи на алгебраических решетках и оформленный в виде стандарта FIPS 204, и алгоритм Sphincs+ (SLH-DSA), базирующийся на схеме Винтерница и оформленный в виде стандарта FIPS 205.

Что касается хэш-функций, то здесь дело обстоит проще. Существует алгоритм Гровера для квантовых компьютеров, который позволяет обеспечить так называемое квадратичное ускорение. Другими словами, чтобы найти прообраз хэша, потребуется примерно в два раза меньший размер перебора. Поэтому в данном случае нет необходимости придумывать новый алгоритм хэширования. Достаточно перейти, например, с алгоритма SHA-256 на алгоритм SHA-512.