В ответ на вопрос, заданный мне Грегом Купербергом, мне интересно, есть ли какие-нибудь статьи, которые определяют и изучают классы сложности языков, допускающие различные виды доказательств знания . Такие классы, как SZK и NISZK, являются чрезвычайно естественными с точки зрения сложности, даже если мы полностью забыли о нулевом знании и просто определили их с точки зрения их проблем полного обещания. Напротив, на поиске «доказательств знания» я был удивлен, не обнаружив ни одной статьи или конспекта лекции, обсуждающего эту прекрасную концепцию в терминах классов сложности.
Приведите несколько примеров: что можно сказать о подклассе SZK∩MA∩coMA, состоящем из всех языков L, которые допускают статистические доказательства с нулевым знанием для x∈L или x∉L, которые также являются доказательствами свидетельства, доказывающего x ∈L или x∉L? Конечно, этот класс содержит такие вещи, как дискретный лог, но мы не можем доказать, что он содержит изоморфизм графов, не помещая GI в coMA. Охватывает ли класс все SZK∩MA∩coMA? Можно также спросить: если существуют односторонние функции, то допускает ли каждый язык L∈MA∩coMA вычислительное доказательство с нулевым знанием, это также доказательство знания свидетеля, доказывающего x∈L или x∉L? (Мои извинения, если один или оба из них имеют тривиальные ответы - я просто пытаюсь проиллюстрировать то, что можно было бы спросите, однажды решили взглянуть на PoK с точки зрения теории сложности.)
источник
Ответы:
Это не фактический ответ; Я просто делюсь некоторыми результатами (которые не вписываются в один комментарий).
Некоторые открытые проблемы (возможно, решенные, но не те, которые я знаю) относительно теоретико-сложных аспектов ПО:
Различные меры эффективности для ZK PoKs определенного отношения с определенной сложностью (например, отношение в AM):
Сложность отношений, допускающих ZK PoK с некоторыми ограничениями, скажем, ограниченные круглые сложности (Itoh и Sakurai рассматривают только ZK PoK с постоянным округлением). Другим примером является случай, когда доказатель имеет полиномиальное время: он не может использовать сокращение до 3-цветности, так как он не может решить NP-полные отношения. Все NP-полные проблемы имеют сокращение Кука от поиска до решения. Тем не менее, согласно приведенному выше результату Белларе-Гольдвассера, такие сокращения не обязательно существуют для всех языков / отношений НП.
Прежде чем закончить, позвольте мне упомянуть, что на самом деле существует несколько определений для PoK, некоторые из которых приведены ниже:
1) Ранние попытки: Фейге, Фиат и Шамир ( J. Cryptology, 1988 ), Томпа и Уолл ( FOCS 1987 ) и Фейге и Шамир ( STOC 1990 ).
2) Стандарт де-факто: Белларе и Голдрайх ( CRYPTO '92 ). В этой статье рассматриваются ранние попытки определения PoK, отмечаются их недостатки и предлагается новое определение, которое можно рассматривать как «определение» PoK. Это определение имеет природу черного ящика (экстрактор знаний имеет доступ к черному ящику с проверяющим).
3) Консервативное ПО: определено Халеви и Микали ( ePrint Archive: Report 1998/015 ), это определение дополняет предыдущее определение, чтобы гарантировать выполнимость. В нем также дается определение знания одного прувера, что хорошо при ответе на вопрос «что значит сказать, что P что-то знает?»
4) Аргументы знания с извлечением , не относящимся к черному ящику. Как упомянуто выше, стандартное определение PoK - это черный ящик, который делает невозможным получение сбрасываемых доказательств (или аргументов) с нулевым знанием для нетривиальных языков. Барак и соавт. ( FOCS 2001 ) дают определение, не относящееся к черному ящику, которое основано (но отличается от) от определения Фейге и Шамира (STOC 1990), приведенного выше.
источник