Исчерпывающий симулятор протоколов нулевого знания в модели случайного Oracle

13

В статье под названием «Об отрицании в общей эталонной строке и случайной модели Oracle» Рафаэль Пасс пишет:

Мы отмечаем, что при проверке безопасности в соответствии со стандартным определением нулевого знания в модели RO [Random Oracle], симулятор имеет два преимущества по сравнению с симулятором простой модели, а именно:

  1. Симулятор может видеть, какие значения сторон запрашивают оракула.
  2. Симулятор может отвечать на эти запросы любым способом, который он выберет, если ответы «выглядят» нормально.

Первый метод, а именно способность «отслеживать» запросы к RO, очень распространен во всех работах, относящихся к концепции нулевого знания в модели RO.

Теперь рассмотрим определение черного ящика с нулевым знанием ( PPT обозначает вероятностную машину Тьюринга за полиномиальное время ):

PPT-симулятор S , такой, что (возможно, мошеннический) PPT-верификатор V , общий вход x L и случайность r , следующие неразличимы:SVxLr

  • вид при взаимодействии с прувером P на входе x и использовании случайности r ; VPxr
  • вывод на входы x и r , когда S предоставляется черный ящик доступа к V . SxrSV

Здесь я хочу показать обманщик , работа которого состоит в том, чтобы исчерпать любой симулятор, который пытается отслеживать запросы RO:V

Пусть будет симулятором, гарантированным экзистенциальным квантификатором в определении нулевого знания черного ящика, и пусть q ( | x | ) будет полиномом, который ограничивает время работы S на входе x . Предположим, что S пытается отслеживать запросы V к RO.Sq(|x|)SxSV

Теперь рассмотрим обман , который сначала запрашивает RO для q ( | x | ) + 1 раз (на произвольных входах по своему выбору), а затем действует произвольно злонамеренно.Vq(|x|)+1

Очевидно, что исчерпывает имитатор S . Простой способ для S состоит в том, чтобы отказаться от такого злонамеренного поведения, но таким образом различающий может легко отличить реальное взаимодействие от имитируемого. (Поскольку в реальном взаимодействии проверяющий P не может отслеживать запросы V ' и, следовательно, не будет отклонять, основываясь на том факте, что V ' запрашивает слишком много.)VSSPVV

Какой обходной путь для вышеуказанной проблемы?

Редактировать:

Хороший источник для изучения ZK в модели RO:

Мартин Гань, Исследование модели случайного Оракула, к.т.н. Диссертация, Калифорнийский университет, Дэвис , 2008, 109 страниц. Доступно на ProQuest: http://gradworks.umi.com/33/36/3336254.html

В частности, он дает определения черного ящика ZK в модели RO в разделе 3.3 (стр. 20), приписываемого Юнгу и Чжао:

Моти Юнг и Юньлэй Чжао. Интерактивное нулевое знание с ограниченным случайным оракулом. В теории криптографии - TCC 2006 , LNCS 3876, с. 21-40, 2006.

М.С. Дусти
источник
Я думаю, что вы могли бы иметь в виду «исчерпывающий» вместо «исчерпывающий».
Дэйв Кларк
Позволю себе не согласиться. Я имел в виду, что нашел способ «исчерпать» симулятор протоколов ZK ... Нет такого понятия, как «исчерпывающий» симулятор.
MS Dousti
Виноват. Я читаю утомительно как прилагательное, а не глагол.
Дэйв Кларк

Ответы:

10

Возникает вопрос, почему можно определить черный ящик ZK в модели случайного оракула. Есть по крайней мере две причины, по которым люди предложили определение нулевого знания черного ящика:

1) Для положительного результата, когда вы говорите, что симулятор является «черным ящиком с нулевым знанием», он автоматически дает вам хорошую оценку времени его работы (т. Е. , в отличие от р о л у ( т я т е ( V * ) ) ) , а также может быть полезно знать , что тренажер не «смотреть на кишках из V * и не , если не все равно V poly(|x|)time(V)poly(time(V))VVреализован с использованием ОЗУ, схемы и т. д. Хотя имитатор модели случайного оракула может быть эффективным, он явно не является черным ящиком, потому что он должен каким-то образом посмотреть на выполнение и понять из него, когда V оценивает хеш-функция. По этой причине есть смысл, в котором нет смысла говорить, что симулятор случайного оракула - это «черный ящик».VV

2) Для получения отрицательного результата люди используют «симулятор черного ящика» для захвата большого класса методов доказательства. В этом случае вы можете определить симулятор черного ящика также в модели случайного оракула, и определение, которое имеет смысл, - это то, что сказал Дэвид. В самом деле, для отрицательного результата даже не в модели случайного оракула, то лучше , если результат имеет место , даже если вы позволите имитатора время работы. В самом деле, хотя это не всегда указано, все отрицательные результаты, о которых я знаю, обладают этим свойством, так как проверяющий обманщик V poly(time(V))V обычно это алгоритм с фиксированным полиномом, который запускает некоторые псевдослучайные функции, в то время как симулятор может иметь любое время выполнения полинома.

Боаз Барак
источник
1
То же самое относится к "универсальной симуляции" ZK? В конце концов, черный ящик ZK - это тип ZK с универсальным моделированием, время работы которого фиксируется до определения . (Тем не менее, не черный ящик ZK является типом универсального моделирования ZK, в котором S может смотреть на «кишки» V *)V
MS Dousti
Пожалуйста, смотрите отредактированный вопрос для некоторых ссылок.
MS Dousti
1
VV
1
Я отложил ответ на ваш комментарий, так как хотел больше узнать. В частности, я прочитал статью Юнга и Чжао (цитированную выше) и отметил, что они использовали черный ящик ZK в модели RO для положительного результата, в то время как вы сказали: «Нет смысла говорить, что модель случайного оракула симулятор "черный ящик". " Является ли их результат философски проблематичным, или мы должны ослабить определение черного ящика?
MS Dousti
4

Вот мой взгляд на проблему. В последнее время я не читал ни одной статьи, посвященной черному ящику с нулевым знанием в модели случайного оракула (RO), поэтому я просто догадываюсь о том, что они имеют в виду, а не о том, что там написано. Короткий ответ (предположение) состоит в том, что BB-ZK в модели RO должен позволять симулятору работать во временном полиноме от | x | и количество запросов RO, выданных V *, читером-обманщиком.

Давайте попробуем обосновать это предположение. Первоначальное наблюдение заключается в том, что термин «черный ящик с нулевым знанием в модели случайного оракула» нуждается в более внимательном рассмотрении для правильного определения. Симуляторы черного ящика определены для работы с любым оракулом (т. Е. С читером-обманщиком как с черным ящиком), и их единственный интерфейс - через ввод / вывод оракула. Если мы просто расширим эту модель, чтобы дать RO всем сторонам (возможно, позволив их каналам иметь ворота RO), то мы получим модель, в которой симулятор не может запрограммировать RO - для запроса оракула, все (включая запросы RO) просто происходит "внутри" оракула V *, а затем возвращает следующее сообщение. Если мы хотим разрешить программирование RO, нам нужно изменить интерфейсы: теперь симулятор получает оракул ввода / вывода для V *, а не случайный оракул. При каждом обращении к оракулу V *, вместо создания следующего сообщения оракул может вместо этого произвести следующий запрос к RO, и симулятор может дать ему ответ RO, вызвав оракула снова. Теперь это позволяет программировать RO, и мы также можем позволить времени работы симулятора зависеть от количества запросов к RO.

Любое дальнейшее исследование значения этих определений оставлено читателю. Я думаю, синтаксически.

Дэвид Кэш
источник
1
Спасибо за ответ, Дэвид. Независимо от способности симулятора программировать RO, он должен иметь возможность «контролировать» их. Таким образом, каждый оракульный запрос от V * тратит время М как минимум на время. Ваша большая идея состоит в том, чтобы изменить модель так, чтобы «позволить симулятору работать во временном полиноме по | x | и количеству запросов RO, выданных V *». Это не стандартная модель, но я считаю ее разумным решением. Тем не менее, я думаю, что «гиганты» в сообществе должны сначала подтвердить подлинность такой модели ...
MS Dousti
1
Можете ли вы привести источник, который точно определяет «стандартную модель»? (Этот термин часто используется как синоним «никаких случайных оракулов или других подобных модификаций в модели вычислений», но я не думаю, что это то, что вы имели в виду.) Я ожидаю, что я набросал определение из того, что считается стандартным, а если нет, то мы можем понять это без каких-либо «гигантов», активно подтверждающих наши рассуждения.
Дэвид Кэш
1
Конечно, под «стандартной моделью» я подразумевал «стандартное определение» ZK под моделью RO. Вы можете сослаться на статью Рафаэля Пасс (цитируется в вопросе), или его магистерскую диссертацию (озаглавленную «Альтернативные варианты доказательств с нулевым знанием»), или статью Ви в AsiaCrypt 2009 («Нулевое знание в случайной модели Oracle, пересмотрено») , Ни один из них не определил «черный ящик» ZK в модели RO (все они упоминали вспомогательный вход ZK), хотя ни один из них не ссылался на «выполнение во времени полинома от | x | и количество запросов RO, выполненных V *». Следовательно, я думаю, что вы выдвигаете новое определение (Google это!)
MS Dousti
Пожалуйста, смотрите отредактированный вопрос для некоторых ссылок.
MS Dousti