Задний план
Следующий контрпример с нулевым разглашением (ZK) описан в работе Канетти [1].Безопасность и состав криптографических протоколов: Учебное пособие, стр. 26], чтобы показать, что существует некоторый протокол, безопасный в автономной модели, но небезопасный в модели UC:
Предположим, что существует такая «система головоломок», что и доказывающая, и проверяющая могут эффективно генерировать головоломки, и
- Доказывающий может эффективно решить любую заданную головоломку, и
- Верификатор не может эффективно (i) решать головоломки или (ii) различать действительное решение или случайное недопустимое для данной головоломки, даже если головоломка генерируется сама по себе.
Теперь, учитывая протокол ZK $\пи$ для некоторого NP-отношения $R$, мы можем построить другой протокол $\пи'$ куда
- Доказывающий и проверяющий работают $\пи$,
- Доказывающий отправляет случайную головоломку $р$ к проверяющему,
- Верификатор отвечает «предполагаемым» решением $s$ за $р$, плюс головоломка $р'$,
- Если $s$ является правильным решением для $р$, доказывающий раскрывает своего тайного свидетеля $w$ (в протоколе ЗК $\пи$) проверяющему. В противном случае доказывающий отправляет решение $s'$ за $р'$ к проверяющему.
Мои вопросы по безопасности в автономной модели
Как утверждается в работе Канетти, если $\пи$ это ЗК в автономный настройка, то так и есть $\пи'$. Чтобы увидеть это, я предполагаю, что $\пи$ надежно реализовать функциональность ZK $\mathcal{F}_{\textf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$ в автономном режиме и попытайтесь показать, что $\пи'$ также надежно реализует $\mathcal{F}_{\textf{zk}}^R: ((x, w), x) \rightarrow (\lambda, R(x, w))$. В частности, если проверяющий является злонамеренным в $\пи'$, я могу построить следующий симулятор $\mathcal{S}_V$ что внутри управляет реальным противником $\mathcal{А}$:
- $\mathcal{S}_V$ вызывает симулятор для $\пи$ для создания $\пи$части стенограммы между честным доказывающим и злонамеренным проверяющим (или, что то же самое, мы можем перефразировать это в $\mathcal{F}_{\textf{zk}}^R$-гибридная модель),
- $\mathcal{S}_V$ отправляет случайную головоломку $р$ к $\mathcal{А}$,
- $\mathcal{S}_V$ получает пару $(с, п')$ от $\mathcal{А}$,
- Если $s$ является правильным решением для $р$, $\mathcal{S}_V$ прерывает. В противном случае, $\mathcal{S}_V$ отправляет решение $s'$ за $р'$ к $\mathcal{А}$.
Понятно, что если только $\mathcal{S}_V$ прерывания, идеальное выполнение в присутствии $\mathcal{S}_V$ неотличим от реального исполнения в присутствии $\mathcal{А}$. С предположением (i) мы можем видеть, что это прерывание происходит с незначительной вероятностью. Следовательно, $\пи'$ защищен от вредоносного верификатора и, следовательно, ZK.
Вопрос 1:
Что меня смущает, так это то, что приведенное выше доказательство не требует предположения (ii). Действительно, Канетти утверждал, что
Кроме того, тот факт, что $P$ (т. е. прувер) обеспечивает $В$ (т. е. верификатор) с решением $s'$ к головоломке $р'$ на самом деле не проблема в автономном режиме, так как $В$ не могу отличить $s'$ из случайного значения (которое $В$ мог возникнуть сам по себе).
Как это предположение помогает установить ZK-свойство $\пи'$ в автономном режиме?
Мое понимание:
Для меня последовательное выполнение $\пи'$ (даже для тех же входных данных) остаются ZK, так как честный доказывающий выбирает случайную головоломку $р$ каждый раз.Эти головоломки отличаются от тех, решения которых известны злоумышленнику-проверяющему с подавляющей вероятностью (в зависимости от пространства головоломок). Следовательно, проверяющий не может использовать эти известные головоломки, чтобы заставить доказывающего выводить свидетеля с немалой вероятностью при последовательном выполнении задач. $\пи'$.
Конечно, чтобы включить предположение (ii) в доказательство, кажется, что мы можем изменить $\mathcal{S}_V$ чтобы на последнем шаге $\mathcal{S}_V$ отправляет случайное решение $s'$ к $\mathcal{А}$ (а не действительное решение для $р'$). Без ограничения общности считаем, что $\mathcal{А}$ выводит свое представление в этом случае. Тогда мы видим, что решение $s'$ входит в $\mathcal{А}$взгляд. Для обеспечения защиты от вредоносных программ в автономной модели используется случайное решение. $s'$ в симуляции должны быть неотличимы от реального исполнения. Однако предположение о неспособности верификатора различить решения НЕ МОЖЕТ быть переведено в то, что различитель (который различает идеальное и реальное исполнения) не может отличить реальное решение от случайного. Следовательно, предположение (ii) кажется беспомощным, поскольку различающий все еще может эффективно различать два мира, наблюдая решение $s'$ в $\mathcal{А}$взгляд.
На мой взгляд, эта проблема может возникнуть из-за того, что между допущениями (i) и (ii) существует редукция, как и между допущениями CDH и DDH. Это сокращение делает одно из двух предположений излишним. Это правильное понимание?
Мои вопросы по безопасности в модели UC
Как утверждается в работе Канетти, $\пи'$ небезопасен в модели UC, так как два одновременных выполнения $\пи'$ с тем же вводом $(х, ш)$ может слить свидетеля $w$ вредоносному верификатору. В частности, атака работает следующим образом:
$В$ сначала ждет, чтобы получить головоломки $p_1$ и $p_2$ от $P$ в двух сессиях. Затем он отправляет $(с, р_2)$ к $P$ в первой сессии, для некоторого произвольного $s$. В ответ, $В$ получает от $P$ решение $s_2$ к $p_2$, к которому он возвращается $P$ во втором сеансе. С $s_2$ правильное решение, $P$ теперь будет раскрывать $w$.
Предположим, что $\пи$ надежно реализует $\mathcal{F}_{\textf{zk}}^R$ в модели UC и пересмотреть эту ненадежность с точки зрения доказательства безопасности. Теперь мы можем рассмотреть симулятор $\mathcal{S}_V'$ в модели УК. В частности, $\mathcal{S}_V'$ идентичен $\mathcal{S}_V$ за исключением того, что это внешне взаимодействует с окружающей средой машины $\mathcal{Z}$ который действует как злонамеренный верификатор (а не внутри взаимодействие с $\mathcal{А}$). С $\пи'$ НЕ является UC-безопасным, $\mathcal{S}_V'$ должен прерваться на последнем шаге с пренебрежимо малой вероятностью. Другими словами, $\mathcal{Z}$ должен быть в состоянии эффективно решить головоломку $р$ проверено честным испытателем. $\mathcal{Z}$ более информирован, чем $\mathcal{А}$ в автономной модели, так как решение $s$ выбран $\mathcal{Z}$ зависит не только от его просмотра в текущем сеансе, но и от других параллельных. Таким образом, возможны два пути $\mathcal{Z}$ решать $р$: (а) $\mathcal{Z}$ решает $р$ сам по себе, или (б) $\mathcal{Z}$ не может эффективно решить $р$ но использует другие сеансы для ее решения. Атака относится к случаю (b).
Вопрос 2:
Даже если предположить, что $\mathcal{Z}$ не может запустить случай (b) атаку, не так ли? $\пи'$ все еще не уверены в модели UC? Для меня, если $\mathcal{Z}$ может следовать коду честного доказывающего, чтобы решить $р$ и предположение (i) относительно верификатора не применяется к $\mathcal{Z}$. В таком случае, $\mathcal{Z}$ может использовать случай (а) атаки, чтобы различить два мира.
В более общем плане, если мы сделаем некоторые предположения о поврежденных сторонах в модели UC, применимы ли эти предположения к машине среды? $\mathcal{Z}$ что контролирует эти партии? Обратите внимание, что в автономной модели различитель и противник являются разными объектами. Напротив, различающий и противник оба являются машиной среды. $\mathcal{Z}$ в модели УК.
Вопрос 3:
Чтобы формально утверждать, что протокол безопасен в модели UC, должны ли мы явно перечислить все возможные способы $\mathcal{Z}$ создавать свои исходящие сообщения на основе своих представлений о произвольных асинхронных выполнениях (возможно, неограниченного количества) сеансов?
Я читал некоторые доказательства UC, но в большинстве из них явно не упоминается асинхронное выполнение сеансов. Так как протоколы над другими сессиями могут быть произвольными, я думаю, что перечислить невозможно $\mathcal{Z}$сообщения на основе $\mathcal{Z}$просмотров всех сессий. Итак, как мы можем убедиться, что $\mathcal{Z}$, пересылаемые в симулятор, не подведут симуляцию, когда мы напишем доказательство безопасности в модели UC?
