Рейтинг:1

Почему zk-STARK квантово безопасен?

флаг us

У меня есть приблизительное представление о том, как работает STARK, но я хочу знать, что делает их квантово безопасными. Это потому, что когда доказывающая сторона генерирует доказательство, она использует случайное число из корня Меркла, которое не может быть угадано квантовым алгоритмом?

Рейтинг:1
флаг ru

Единственный криптографический примитив, необходимый для zk-STARK, — это криптографически безопасная хэш-функция, которую мы будем обозначать $Ч$. Все известные квантово-уязвимые формы криптографии зависят от какого-то другого криптографического примитива.

Чтобы предотвратить генерацию недействительных доказательств, хэш-функция $Ч$ должен быть устойчивым к предварительному изображению, т.е. для целевого вывода $у$ должно быть трудно найти вход $х$ такой, что $Н(х)=у$. Теперь, если мы ничего не знаем о функции $Ч$ Помимо результатов, которые он производит, это пример неструктурированной задачи поиска, которую можно решить с помощью Алгоритм Гровера на достаточно большом и стабильном квантовом компьютере за время, примерно пропорциональное квадратному корню из пространства изображения. На самом деле мы знаем, что алгоритм Гровера — это, по существу, наилучший подход к таким проблемам. Однако алгоритм Гровера крайне непараллелен (для выполнения поиска за 1/10 времени нам нужно использовать квантовые компьютеры со 100-кратным увеличением), и утверждается, что поиск решений для 256-битных пространств изображений невозможен для любой разумный прогноз возможностей квантовых вычислений.

На практике хеш-функция, такая как SHA256, используется в zk-STARK, для которых мы знаем все вычислительные детали. Тем не менее, никому не удалось продемонстрировать какую-либо структуру в SHA256, которая привела бы к подходу, превосходящему подход Гровера. Вера в силу SHA256 такова, что он используется в качестве одного из эталонов в процессе постквантовой криптографии NIST (безопасность уровня 2 определяется как требующая для взлома не меньше ресурсов, чем обнаружение коллизии SHA256; см. конкурс предложений раздел 4.A.5).

Даже если бы SHA256 действительно демонстрировал признаки структуры, которая позволяет проводить превосходные атаки на Гровера, существует множество других хеш-функций, которые можно легко интегрировать в структуру zk-STARK. По всем этим причинам существует высокая уверенность в квантовой безопасности структуры zk-STARK.

Ответить или комментировать

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