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

Осмысление различных протоколов и методов их построения привело в 1985–1986 гг. к появлению двух плодотворных математических моделей — интерактивной системы доказательства и доказательства с нулевым разглашением.

Математические исследования этих новых объектов позволили доказать несколько утверждений, весьма полезных при разработке криптографических протоколов.

Под интерактивной системой доказательства (P, V, S) понимают протокол взаимодействия двух абонентов: P (доказывающий) и V (проверяющий).

Абонент P хочет доказать V, что утверждение S истинно.

При этом абонент Vсамостоятельно, без помощи P, не может доказать утверждение S(поэтому Vи называется проверяющим).

Абонент P может быть и противником, который хочет доказать V, что утверждение S истинно, хотя оно ложно.

Протокол может состоять из многих раундов обмена сообщениями между P и V и должен удовлетворять двум условиям:

1) полнота — если S действительно истинно, то абонент P почти наверняка убедит абонента V признать это;

2) корректность — если S ложно, то абонент P вряд ли убедит абонента V, что S истинно.

Здесь словами «почти наверняка» и «вряд ли» заменены точные математические формулировки, использующие понятие вероятности.

Подчеркнем, что в определении системы (P, V, S) не допускалось, что V может быть противником. А если V оказался противником, который хочет «выведать» у Pкакую-нибудь новую полезную для себя информацию об утверждении S?

В этом случае P, естественно, может не хотеть, чтобы это случилось в результате работы протокола (P, V, S).

Протокол (P, V, S), решающий такую задачу, называется «доказательством с нулевым разглашением» и должен удовлетворять, кроме условий 1 и 2, еще и следующему условию:

3) нулевое разглашение (или стойкость) — в результате работы протокола (P, V, S) абонент V не увеличит свои знания об утверждении Sили, другими словами, не сможет извлечь никакой информации о том, почему S истинно.

Самое удивительное, что в 1991 году для широкого класса математических проблем (включающего так называемые NP-полные задачи) удалось доказать существование доказательств с нулевым разглашением. Впрочем, это доказано только в предположении, что существует односторонняя функция.

Приведем одно практическое применение теории доказательств с нулевым разглашением— «интеллектуальные карточки» (неподделываемые удостоверения личности, кредитные карточки и т.п.).