Сколько кубитов потребуется для взлома криптографических алгоритмов с открытым ключом?

Исследователи Google опубликовани препринт, демонстрирующий, что 2048-битное RSA-шифрование "теоретически может быть взломано квантовым компьютером с 1 миллионом зашумленных кубитов, работающим в течение недели", – сообщает блог Google Security.

"Это 20-кратное снижение количества кубитов по сравнению с нашей предыдущей оценкой, опубликованной в 2019 году..."

Снижение количества физических кубитов обусловлено двумя факторами: улучшенными алгоритмами и улучшенной коррекцией ошибок, при которой кубиты, используемые алгоритмом ("логические кубиты"), избыточно кодируются на множестве физических кубитов, чтобы ошибки могли быть обнаружены и исправлены. Исследователи Google нашли способ уменьшить операции в алгоритме 2024 года в 1000 раз по сравнению с предыдущими разработками – до всего лишь 2x. А "ключевым изменением в области коррекции ошибок стало утроение плотности хранения неактивных логических кубитов за счет добавления второго уровня коррекции ошибок".

Важно отметить, что квантовые компьютеры с соответствующими показателями ошибок в настоящее время имеют порядка 100–1000 кубитов, а Национальный институт стандартов и технологий (NIST) недавно опубликовал стандартные PQC-алгоритмы, которые, как ожидается, будут устойчивы к будущим крупномасштабным квантовым компьютерам. Однако этот новый результат подчеркивает важность перехода к этим стандартам в соответствии с рекомендованными NIST сроками.

В статье отмечается, что Google начал использовать стандартизированную версию ML-KEM сразу после ее появления, как внутри компании, так и для шифрования трафика в Chrome.

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