Доказательство с нулевым разглашением

 

Цель: Доказывающий (Д) должен убедить проверяющего (П) в наличии у него ключа от двери C-D

1) Начало: Д - в точке В, П - в точке А

2) Д переходит случайным образом в С или D.

3) П просит Д выйти из правого (левого) коридора.

4) Д выполняет просьбу П, при необходимости воспользовавшись имеющимся ключом.

При отсутствии ключа вероятность угадывания 1А

5) Если Д правильно выполнил запрос, то итерация считается успешной, если не смог правильно выполнить - то доказательство отвергается.

6) Итерация 1)-5) повторяется n, пока не будет достигнута требуемая достоверность 1-(1/2)An. При достижении заданного уровня достоверности доказательство принимается.

Формальное определение в терминах машин Тьюринга (МТ)

Интерактивным доказательством для языка L называется пара интерактивных МТ (P(x), V(x)), где P - моделирует доказывающего, V - моделирует проверяющего, х - входное слово допустимого МТ языка L, [P(x), V(x)] - слово на выходе

Полнота

Если оба участника следуют протоколу, то доказательство будет принято

Корректность  и полинома p, при  достаточно большой длины

Если противник будет пытаться доказывать ложное утверждение, как угодно отклоняясь от протокола, то вероятность успеха для него пренебрежимо мала.

Нулевое разглашение

Для любой полиномиальной вероятностной МТ V*, существует вероятностная МТ M_V* работающая в среднем за полиномиальное время, т.ч

MV* (x) = [ P(x), V*(x)]

Защищает доказывающего am нечестного проверяющего:

Как бы ни отклонялся проверяющий от действий, предписанных протоколом (использует V * вместо V), он сможет при этом получить только такую информацию, которую и сам может самостоятельно вычислить в среднем за полиномиальное время.