Во всём виноваты «котики»: новый алгоритм и кошачьи кубиты приблизили квантовый взлом биткоин-кошельков

Рано или поздно это случится — квантовые компьютеры смогут вскрывать коды и ключи к криптовалютным кошелькам. Предыдущая оценка Google требовала для этого квантовых платформ с полумиллионом кубитов. Новый анализ компании Alice & Bob показал, что для взлома кошельков биткоина нужно в 17 раз меньше кубитов, что резко приблизило опасность потерять криптовалютные накопления.

Согласно расчётам исследователей французской компании, для атаки может оказаться достаточно машины с 29 588 физическими кубитами. В марте этого года исследователи Google Quantum AI для аналогичных целей предполагали потребность в 500 тыс. кубитах. В обоих случаях речь идёт о теоретических моделях. Прямо сейчас никто не может реализовать их на практике. Собственно, пока даже нет уверенности, что всё это будет работать на реальном квантовом компьютере.

Как обычно, в основе расчёта лежит использование алгоритма Шора для факторизации чисел, что решает задачи, на которых основана криптография с открытым ключом. В случае биткоина речь идёт о выполнении дискретного логарифма для эллиптической кривой P-256, который используется в подписи ECDSA. Если достаточно мощный отказоустойчивый квантовый компьютер решит эту задачу для находящегося в доступе открытого ключа, он сможет восстановить соответствующий закрытый ключ и создать подпись от имени владельца кошелька.

Всё это было известно ранее. Например, ещё весной этого года вышла работа, которая обосновала возможность взлома P-256 всего за несколько дней на квантовой платформе из холодных атомов из 26 000 кубитов. Исследователи из Alice & Bob воспользовались другой платформой — на так называемых кошачьих кубитах (cat qubits), предложенный около пяти лет назад специалистами Amazon.

Считается, что кошачьи кубиты подавляют один из основных типов ошибок — переворот бита (bit-flip), что снижает требование к ресурсам квантовых вычислителей. Тем самым коррекция ошибок в новой архитектуре может быть сосредоточена преимущественно на другом типе ошибок — фазовых переворотах (phase-flip).

Исследователи также применили более эффективные LDPC-коды коррекции ошибок и переработанную схему арифметических операций, необходимых алгоритму Шора.

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

Согласно работе, восстановление закрытого ключа биткоина в новых условиях займёт около часа (61,8 мин). Это дольше среднего десятиминутного интервала между появлением новых блоков биткоина, поэтому атака на транзакцию до её подтверждения в рамках данного сценария определённо не укладывается в отведённое время. Но это не защищает от другой опасности, а именно — от взлома закрытых ключей на основе известных открытых, на что злоумышленникам отпущено гораздо больше времени.

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