В статье под названием «Об отрицании в общей эталонной строке и случайной модели Oracle» Рафаэль Пасс пишет:
Мы отмечаем, что при проверке безопасности в соответствии со стандартным определением нулевого знания в модели RO [Random Oracle], симулятор имеет два преимущества по сравнению с симулятором простой модели, а именно:
- Симулятор может видеть, какие значения сторон запрашивают оракула.
- Симулятор может отвечать на эти запросы любым способом, который он выберет, если ответы «выглядят» нормально.
Первый метод, а именно способность «отслеживать» запросы к RO, очень распространен во всех работах, относящихся к концепции нулевого знания в модели RO.
Теперь рассмотрим определение черного ящика с нулевым знанием ( PPT обозначает вероятностную машину Тьюринга за полиномиальное время ):
PPT-симулятор S , такой, что ∀ (возможно, мошеннический) PPT-верификатор V ∗ , ∀ общий вход x ∈ L и ∀ случайность r , следующие неразличимы:
- вид при взаимодействии с прувером P на входе x и использовании случайности r ;
- вывод на входы x и r , когда S предоставляется черный ящик доступа к V ∗ .
Здесь я хочу показать обманщик , работа которого состоит в том, чтобы исчерпать любой симулятор, который пытается отслеживать запросы RO:
Пусть будет симулятором, гарантированным экзистенциальным квантификатором в определении нулевого знания черного ящика, и пусть q ( | x | ) будет полиномом, который ограничивает время работы S на входе x . Предположим, что S пытается отслеживать запросы V ∗ к RO.
Теперь рассмотрим обман , который сначала запрашивает RO для q ( | x | ) + 1 раз (на произвольных входах по своему выбору), а затем действует произвольно злонамеренно.
Очевидно, что исчерпывает имитатор S . Простой способ для S состоит в том, чтобы отказаться от такого злонамеренного поведения, но таким образом различающий может легко отличить реальное взаимодействие от имитируемого. (Поскольку в реальном взаимодействии проверяющий P не может отслеживать запросы V ' и, следовательно, не будет отклонять, основываясь на том факте, что V ' запрашивает слишком много.)
Какой обходной путь для вышеуказанной проблемы?
Редактировать:
Хороший источник для изучения ZK в модели RO:
Мартин Гань, Исследование модели случайного Оракула, к.т.н. Диссертация, Калифорнийский университет, Дэвис , 2008, 109 страниц. Доступно на ProQuest: http://gradworks.umi.com/33/36/3336254.html
В частности, он дает определения черного ящика ZK в модели RO в разделе 3.3 (стр. 20), приписываемого Юнгу и Чжао:
Ответы:
Возникает вопрос, почему можно определить черный ящик ZK в модели случайного оракула. Есть по крайней мере две причины, по которым люди предложили определение нулевого знания черного ящика:
1) Для положительного результата, когда вы говорите, что симулятор является «черным ящиком с нулевым знанием», он автоматически дает вам хорошую оценку времени его работы (т. Е. , в отличие от р о л у ( т я т е ( V * ) ) ) , а также может быть полезно знать , что тренажер не «смотреть на кишках из V * и не , если не все равно V ∗poly(|x|)⋅time(V∗) poly(time(V∗)) V∗ V∗ реализован с использованием ОЗУ, схемы и т. д. Хотя имитатор модели случайного оракула может быть эффективным, он явно не является черным ящиком, потому что он должен каким-то образом посмотреть на выполнение и понять из него, когда V ∗ оценивает хеш-функция. По этой причине есть смысл, в котором нет смысла говорить, что симулятор случайного оракула - это «черный ящик».V∗ V∗
2) Для получения отрицательного результата люди используют «симулятор черного ящика» для захвата большого класса методов доказательства. В этом случае вы можете определить симулятор черного ящика также в модели случайного оракула, и определение, которое имеет смысл, - это то, что сказал Дэвид. В самом деле, для отрицательного результата даже не в модели случайного оракула, то лучше , если результат имеет место , даже если вы позволите имитатора время работы. В самом деле, хотя это не всегда указано, все отрицательные результаты, о которых я знаю, обладают этим свойством, так как проверяющий обманщик V ∗poly(time(V∗)) V∗ обычно это алгоритм с фиксированным полиномом, который запускает некоторые псевдослучайные функции, в то время как симулятор может иметь любое время выполнения полинома.
источник
Вот мой взгляд на проблему. В последнее время я не читал ни одной статьи, посвященной черному ящику с нулевым знанием в модели случайного оракула (RO), поэтому я просто догадываюсь о том, что они имеют в виду, а не о том, что там написано. Короткий ответ (предположение) состоит в том, что BB-ZK в модели RO должен позволять симулятору работать во временном полиноме от | x | и количество запросов RO, выданных V *, читером-обманщиком.
Давайте попробуем обосновать это предположение. Первоначальное наблюдение заключается в том, что термин «черный ящик с нулевым знанием в модели случайного оракула» нуждается в более внимательном рассмотрении для правильного определения. Симуляторы черного ящика определены для работы с любым оракулом (т. Е. С читером-обманщиком как с черным ящиком), и их единственный интерфейс - через ввод / вывод оракула. Если мы просто расширим эту модель, чтобы дать RO всем сторонам (возможно, позволив их каналам иметь ворота RO), то мы получим модель, в которой симулятор не может запрограммировать RO - для запроса оракула, все (включая запросы RO) просто происходит "внутри" оракула V *, а затем возвращает следующее сообщение. Если мы хотим разрешить программирование RO, нам нужно изменить интерфейсы: теперь симулятор получает оракул ввода / вывода для V *, а не случайный оракул. При каждом обращении к оракулу V *, вместо создания следующего сообщения оракул может вместо этого произвести следующий запрос к RO, и симулятор может дать ему ответ RO, вызвав оракула снова. Теперь это позволяет программировать RO, и мы также можем позволить времени работы симулятора зависеть от количества запросов к RO.
Любое дальнейшее исследование значения этих определений оставлено читателю. Я думаю, синтаксически.
источник