В ответ на вопрос, заданный мне Грегом Купербергом, мне интересно, есть ли какие-нибудь статьи, которые определяют и изучают классы сложности языков, допускающие различные виды доказательств знания . Такие классы, как SZK и NISZK, являются чрезвычайно естественными с точки зрения сложности, даже...
В главе 10 HAC (10.4.2) мы видим хорошо известный протокол идентификации Фейге-Фиат-Шамира, основанный на доказательстве с нулевым знанием, использующем (предполагаемую) сложность извлечения квадратных корней по модулю композита, который трудно проанализировать. Я дам схему своими словами (и,...
В доказательстве Голдрайха и др. О том, что три цвета имеют нулевое доказательство знания, используется битовое обязательство для полной раскраски графа в каждом раунде [1]. Если граф имеет вершин и ребер, безопасный хеш имеет битов, и мы ищем вероятность ошибки , общая стоимость связи равнае б...
Есть ли способ, которым проверяющий может убедить верификатора в том, что некоторое выражение HORN-SAT выполнимо? Конечно, это может показаться глупым, поскольку для HORN-SAT существуют линейные алгоритмы времени. С другой стороны, HORN-SAT является P-полным, что означает, что он не имеет...