Насколько я знаю, вы поняли суть. «Перемотка назад» - это всего лишь стратегия «упреждения», ставшая возможной благодаря доступу оракула симулятора к верификатору.
Его обычно называют «сверхспособностью», потому что это способность, которой доказывающий не имеет во время обычного выполнения протокола, в противном случае надежность может быть скомпрометирована (поскольку симулятор может создать убедительную расшифровку взаимодействия, ничего не зная, он может выдать себя за мошенника). доказывающий, делающий вид, что доказывает ложное утверждение)
Что касается того факта, что симуляция — это как раз то, что верификатор может сделать в одиночку, это правда: симулянт ничего не должен знать, чтобы доказать ZKness, и кто может быть лучшим кандидатом, чем верификатор, на роль того, кто не знает?!
РЕДАКТИРОВАТЬ, ЧТОБЫ ОТВЕТИТЬ ПОСЛЕДУЮЩИЙ КОММЕНТАРИЙ:
В главе 6 Учебных пособий по основам криптографии (Springer) Иегуда Линделл пишет:
Во-первых, может возникнуть вопрос, как можно «технически» перемотать верификатор. На самом деле, если рассматривать нулевое знание черного ящика, это тривиально. В частности, имитатору предоставляется доступ оракула к функции следующего сообщения V*(x, z, r, ·) верификатора. Это означает, что он предоставляет расшифровку m' = (m1, m2, . . .) входящих сообщений и получает обратно следующее сообщение, отправленное, когда V * имеет вход x, вспомогательный вход z, случайную ленту r и входящие сообщения m'.
так что это просто следующее сообщение, а не весь результирующий расшифровщик в конце взаимодействия (если это было вашим сомнением).
Учитывая приведенное выше определение функции следующего сообщения (где вызов доказывающего относится к сообщениям, ранее полученным верификатором), ваш «очевидный способ» кажется мне неверным для универсального (также известного как потенциально мошеннический) верификатор V *.
Если верификатор честен (поэтому вызов действительно «случайный» — даже если он не обязательно равномерно распределен), вы можете просто изменить порядок, в котором симулятор получает сообщения (то есть сначала результат, затем вызов, затем обязательство): Кстати, это стратегия, чтобы доказать, что протокол идентификации Шнорра является HVZKP (опуская - для простоты - что мы имеем дело с распределениями, а не только с фактическими значениями).
Но если нам приходится иметь дело с потенциально мошенническим верификатором V* (и это предполагаемый случай раздела 8.7 вашей лекции), возможно, проблемы являются функцией обязательств, поэтому они не являются независимыми друг от друга, поэтому ваша лучшая стратегия — попробовать все результаты. пока вы не найдете правильный (или, приняв точку зрения вашей лекции, получив результат, вы начнете пробовать все обязательства, пока функция не выдаст «правильный» вызов) ... в любом случае вам нужно проверить количество случаев, растущих экспоненциально, если у вас есть только одна степень свободы, поэтому PPT Simulator не может справиться с этим, он же ZK, не доказано:
Это означает, что после перемотки симулятора весь протокол как бы начинается заново с нуля. Это означает, что ожидаемое количество перемоток является экспоненциальным, и что мы не можем построить симулятор PPT, а это означает, что мы не можем доказать свойство нулевого разглашения.
Так что имхо нет никакого противоречия между приведенным выше определением перемотки и заключением первого абзаца в разделе 8.7 вашей лекции.
Признаюсь, я мало думал о том, почему симулятор должен быть PPT и не может, скажем так, быть вычислительно неограниченным, по крайней мере, в принципе: я хотел бы услышать об этом от других.
А пока мои обоснованные догадки таковы:
- "мы считаем неразрешимыми те задачи, которые не может выполнить машина ППТ(Голдрайх, Фонд криптографии, том I, стр. 19)
- для любого фактического использования мы всегда вынуждены использовать эффективные объекты (включая пруверы, даже если теоретически нет проблем считать их неограниченными)
- наличие симулятора является достаточным, но не необходимым условием для ZK, поэтому использование этой парадигмы уже означает отсутствие каких-либо наиболее полных предположений: в этом сценарии кажется приемлемым использование чрезмерно предусмотрительного определения.
