Теория и практика защиты программ

Задача «Изоморфизм графа»


Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка «Изоморфизм графов» из работы[GMW]. Входным словом является пара графов G1=(U,Е1) и G0=(U,E0). Здесь U - множество вершин, которое можно отождествить с множеством натуральных чисел {1,...,n}, Е1

и Е0 множества ребер такие, что |Е1|=|Е0|=m. Графы G1 и G2 называются изоморфными, если существует перестановка на множестве U такая, что (u,v)ÎЕ0

тогда и только тогда, когда (j(u),j(v))ÎЕ1

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

Протокол IG

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

1. Р

выбирает случайную перестановку p на множестве U, вычисляет Н=-тG1 и посылает этот граф V.

2. V

выбирает случайный бит a и посылает его Р.

3. Если a=1, то Р посылает V перестановку p, в противном случае - перестановку p°j.

4. Если перестановка, полученная V, не является изоморфизмом между Ga

и Н, то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.

Если проверки п.4 дали положительный результат во всех m циклах, то V

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

Необходимо отметить, что если в протоколе IG машина Р

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

Теорема 4.1. Протокол

IG является доказательством с абсолютно нулевым разглашением для языка «Изоморфизм графов».

Доказательство.

Подробно приведено в работе [Ва1].



Содержание раздела