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