Рейтинг:1

Crypto

Являются ли zk-STARK действительно квантово-устойчивыми?

James

30.12.2022, 12:38

Я вижу много упоминаний о том, что доказательства zk-STARK, которые разрабатываются специально для использования в сетях блокчейнов, помечены как «квантово-устойчивые». Многие статьи и отчеты, в которых говорится об этом, утверждают, что это основано на идее, что zk-STARK полагаются на устойчивые к коллизиям хэши. Однако я понимаю, что никогда не может быть абсолютно устойчивого к коллизиям хэша, и что для квантового компьютера было бы тривиально пытаться найти коллизию в любом хеше. Есть ли какая-то часть, которую я не понимаю, которая делает zk-STARK квантово-устойчивыми?

274

1 + 0

доказательства с нулевым разглашением

криптовалюта

Geoffroy Couteau

30.01.2023, 08:12

Смежный вопрос: [Являются ли криптографические хэш-функции квантово безопасными?] (https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure/44390#44390)

Ответить

Рейтинг:1

Crypto

Mark

30.12.2022, 16:32

Для многих хеш-функций самые известные квантовые атаки основаны на Поиск Гровера. Это ускоряет $О(Н)$ операция по $O(\sqrt{N})$, так и ускорение, но только в "полиномиальный" множитель (не ускоряет $О(2^N)$ операция по $О(Н)$, или что-то подобное).

Насколько я понимаю, никогда не может быть абсолютно устойчивого к коллизиям хэша, и что для квантового компьютера было бы тривиально пытаться найти коллизию в любом хэше.

Часть, которую вы не понимаете, это второе утверждение. Если вы имеете в виду конкретную атаку (которая превосходит все, что основано на поиске Гровера), вы должны попытаться проработать детали, так как это будет довольно хороший результат.

0 + 5

poncho

30.12.2022, 17:14

@James: обратите внимание, что поиск Гровера доказуемо находится в пределах постоянного коэффициента (недалеко от 1) от доказуемо оптимального значения, если вы рассматриваете хеш-функцию как непрозрачный объект. Следовательно, любой результат, который вы можете получить значительно лучше, чем у Гровера, будет зависеть от внутреннего устройства самой хеш-функции.

Ответить

James

30.12.2022, 23:36

Поскольку классические компьютеры могут найти случайную коллизию для хэш-функции в $O(\sqrt{N})$, означает ли это, что и классические, и квантовые компьютеры делают для этого примерно одинаковое количество шагов? Или поиск Гровера занял бы $O(\sqrt{\sqrt{N}})$ шагов вместо того, чтобы найти случайное столкновение?

Ответить

James

30.12.2022, 23:38

У меня также сложилось впечатление, что квантовые компьютеры могут проверять больше возможных результатов за шаг в зависимости от количества кубитов, хотя мои точные знания в этой области немного размыты.

Ответить

Mark

30.12.2022, 23:56

@James [Эти заметки] (https://www.scottaaronson.com/qclec/24.pdf) создают впечатление, что ответ $O(N^{1/3})$. Независимо от точного показателя степени, квантовые вычисления, как известно, не дают здесь суперполиномиального улучшения. И ваше второе впечатление — распространенное непонимание квантовых компьютеров. См., например, [миф 2 этой статьи] (https://cacm.acm.org/magazines/2019/4/235578-cyber-security-in-the-quantum-era/fulltext), что (примерно) то, что вы намекаете.

Ответить

poncho

31.12.2022, 02:40

@Mark: известно, что для поиска коллизий ответ находится между $O(N^{1/3})$ и $O(N^{1/2})$. Если вы считаете только запросы Oracle, то известно, что нижняя граница достижима; однако это связано с довольно высокой стоимостью схемы (настолько высокой, что для практических хеш-функций было бы дешевле распараллелить алгоритм $O(N^{1/2})$). Неизвестно, существует ли менее затратный алгоритм, который достигает (или приближается) к нижней границе.

Ответить

Admin