Как симулятор формирует правильную расшифровку под ХВЗК с эвристикой Fiat-Shamir?

Задний план

Я понимаю интерактивную версию протокола Шнорра и понимаю, как симулятор может генерировать выходные данные, которые i.i.d соответствуют выходным данным доказывающего-верификатора:

Вопрос

Чего я не понимаю, так это того, как симулятор генерирует правильную стенограмму, когда мы переходим на неинтерактивную версию протокола идентификации Шнорра? Страница 4 лекций CS355 2019 г. показывает, что тренажер может «Программировать $Ч(г,ч,у)$ быть $с$".

И 23 стр. следующие конспекты лекций показывает, что симулятор может установить $Ч$ к любой произвольной хеш-функции.

Мне это кажется странным, и я не понимаю. Почему мы предполагаем, что S может выбрать любую хеш-функцию? На самом деле будет некоторая фиксированная хеш-функция, которую мы используем для генерации случайного вызова. $с$, правильно?

Насколько я понимаю, доказательство HVZK не работает, если мы не позволяем симулятору создавать какие-либо хеш-функции. Предполагая, что у нас есть фиксированная хэш-функция, устойчивая к прообразу, симулятор не может генерировать сообщения доказывающего $u$, $z$ способом, соответствующим этой задаче. В интерактивном случае симулятор может выбрать $z$ и $с$ случайным образом и работайте в обратном порядке, чтобы получить $u$ детерминистически где $u = \frac{g^z}{h^c}$. Но в неинтерактивном случае вам нужно найти $u$ и $с$ такой, что $u = \frac{g^z}{h^c}$ И $H(g,h,u) = c$, и это NP-сложно. Таким образом, вы теряете свойство нулевого разглашения, поскольку симулятор не может создать действительную стенограмму.

Так как же на практике реализуются неинтерактивные доказательства знаний с нулевым разглашением?

Список используемой литературы

• https://crypto.stanford.edu/cs355/19sp/lec5.pdf
• Что такое неинтерактивное доказательство с нулевым разглашением?
• Как работает симулятор свойства нулевого разглашения специального добросовестного верификатора?
• Является ли хэш доказательством с нулевым разглашением?
• https://www.impan.pl/konferencje/bcc/2019/19-simons-x/zero_knowledge_primer_2.pdf

Ключевым моментом здесь является то, что при преобразовании Fiat-Shamir вам необходимо провести различие между тем, что означает безопасность в реальной реализации, и тем, что она означает в теории вашего проекта. Это правда, что на практике мы используем хеш-функции для реализации преобразования Фиата-Шамира, но, как вы упомянули, смоделировать доказательство в этом случае не так просто. Теоретически, однако, мы используем идеальный объект, называемый «случайным оракулом», и в зависимости от того, какие свойства мы предполагаем для этого случайного оракула, мы можем выполнять моделирование. Точнее, случайный оракул может быть как программируемым, так и непрограммируемым. Под программируемостью подразумевается, что симулятору разрешено выбирать ответы на запросы оракула. Например, в контексте неинтерактивных доказательств с нулевым разглашением (NIZK) это позволяет симулятору создавать убедительные, но поддельные доказательства.С другой стороны, модель непрограммируемого случайного оракула (NPRO) ограничивает симулятор таким образом, что он больше не может выбирать ответы на запросы. Вместо этого симулятор получает возможность видеть только все пары запрос/ответ, сделанные сторонами во время протокола. Это ограничение симулятора (или, в более общем смысле, снижение безопасности) делает лежащие в его основе доказательства более предпочтительными, поскольку они полагаются на меньшее количество свойств случайного оракула и поэтому могут рассматриваться как шаг к избавлению от него. Но в некоторых доказательствах NIZK, таких как преобразование Фиата-Шамира протокола Шнорра, программирование случайного оракула кажется решающим для обеспечения свойства ZK.