Введение в криптографию
[an error occurred while processing this directive]

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


Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ из работы Гольдрайха, Микали и Вигдерсона []. Входным словом является пара графов и . Здесь - множество вершин, которое можно отождествить с множеством натуральных чисел , и - множества ребер такие, что . Графы и называются изоморфными, если существует перестановка на множестве такая, что тогда и только тогда, когда

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

Протокол IG

Пусть - изоморфизм между и . Следующие четыре шага выполняются в цикле раз, каждый раз с независимыми случайными величинами.

  • P выбирает случайную перестановку на множестве , вычисляет и посылает этот граф V.
  • V выбирает случайный бит и посылает его P.
  • Если , то P посылает V перестановку , в противном случае - перестановку .
  • Если перестановка, полученная V, не является изоморфизмом между и , то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.
  • Если проверки п.4 дали положительный результат во всех

    циклах, то V принимает доказательство.

    Заметим, что если в протоколе IG машина P получает изоморфизм в качестве дополнительного входного слова, то ей для выполнения протокола не требуются неограниченные вычислительные ресурсы. Более того, в этом случае P может быть полиномиальной вероятностной машиной Тьюринга.

    Теорема 2. ([])   Протокол IG является доказательством с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ.

    Полнота протокола IG очевидна.

    Для доказательства корректности достаточно заметить, что бит , который V выбирает на шаге 2, указывает P, для какого из графов - или - требуется продемонстрировать изоморфизм с графом . Если и не изоморфны, то может быть изоморфен, в лучшем случае, одному из них. Поэтому проверка п. 4 даст положительный результат с вероятностью в одном цикле и с вероятностью во всех циклах.




    - Начало -  - Назад -  - Вперед -


    [an error occurred while processing this directive]