Исследователи из Google, Калифорнийского университета в Беркли, Ethereum Foundation и Стэнфордского университета сделали прорыв в квантовых вычислениях, сократив потребность в памяти для взлома 256-битного шифрования на эллиптических кривых в двадцать раз. Для реализации атаки на такую криптографию теперь нужны менее 1200 логических кубитов и 90 миллионов квантовых шлюзов, что примерно соответствует 500 000 физических кубитов. Сложнейшая часть исследования заключается в том, что авторы не опубликовали саму схему, а доказали её существование с помощью нулевого разглашения. Это сделано из страха, что злоумышленники воспользуются открытиями для нарушения безопасности блокчейна Bitcoin или других цифровых систем.
Вместо прямой выдачи алгоритма команда представила проверочные данные и симулятор, способный эмулировать квантовые схемы. Методика опирается на доказательство STARK, которое верифицируется с помощью машины SP1. SP1 моделирует процессор RISC-V, генерируя следы выполнения кода. Эти следы преобразуются в полиномы, и доказательство строится на сложной математической проверке: если атакующий не сможет подобрать случайные точки, совпадающие с результатом, значит, схема работает. Для финальной минимизации доказательства STARK перевели в формат SNARK, используя систему Groth16. Это позволило сжать файл доказательства до 1.7 МБ. Проверка на обычном ноутбуке заняла менее 14 минут с использованием Rust и внешних библиотек, но полный аудит кода затруднён из-за огромного числа зависимостей.
Однако отсутствие реального квантового контура ставит под удар прогресс открытой науки. Учёные доказали, что у них есть способ ускорить алгоритм Шора, но не дают остальным сообществу доступа к деталям. Ситуация усугубляется тем, что безопасность их доказательства SNARK опирается на секретное случайное значение, сгенерированное в 2019 году в рамках консорциума из 176 криптографов Aztec Labs. Если хотя бы один из них честно уничтожил свои данные, то ключ невосстановим. Если же он остался — теория рушится, так как злоумышленник сможет подделать доказательство. Пока неясно, применимы ли эти результаты к другим свежим методам экономии кубитов. Практические квантовые компьютеры всё ещё в годах, но теперь сложно прогнозировать точное время их появления. Эксперты настоятельно рекомендуют внедрять постквантовую криптографию и надеяться, что в будущем исследователи будут делиться реальными схемами, а не просто криптографическими доказательствами их существования.