Чекер для задачи «Изоморфизм графа»
Пусть G и H – два графа и k
– некоторый параметр безопасности. Чекер CGIP(G,H,k) проверяет программу P
на входных графах G и H. На выходе чекера будет результат «Норма», если графы изоморфны и «Сбой», если неизоморфны.
Следующая теорема [BK] определяет эффективность и корректность чекера для решения задачи «ИЗОМОРФИЗМ ГРАФОВ» - IG.
Пусть P – программа, которая останавливается на всех входах и всегда выдает либо «Норма», либо «Сбой». Пусть также G и H - два любых графа и пусть CGIP(G,H;k) – вышеуказанный чекер.
Теорема 4.1. Если P корректная программа для решения задачи IG, тогда чекер CGIP(G,H;k) всегда выдаст на выходе «Норма». Если P - некорректна, т.е. P(G,H)GI(G,H), тогда вероятность Prob{CGIP(G,H;k)=«Норма»}<1/2k.
Доказательство.
Достаточно очевидно и приведено в работе [BK].
Интерактивные системы доказательств и интерактивные системы доказательств с нулевым разглашением [Ва1,Ва2] могут эффективно применяться в системах защиты информации от несанкционированного доступа, например, в схемах интерактивной идентификации пользователей системы [Ка14,КУ4,КУ6]. В целом интерактивный протокол доказательств для задачи IG
может применяться для идентификации, однако для практических целей удобно использовать системы доказательств, основанные на трудности решения некоторых теоретико-числовых задач. Тем более, как было показано выше, существует принципиальная возможность построения самотестирующейся/ самокорректирующейся программной пары, например, для функции дискретного экспоненцирования.
Чекер CGIP(G,H,k)
1. Вычислить P(G,H).
2. Если P(G,H)=«Изоморфизм», тогда использовать P для поиска изоморфизма их G в H. Проверить, является ли результирующее соответствие изоморфизмом. Если нет, тогда подать на выход «Сбой», если является, тогда подать на выход «Норма».
3. Если P(G,H)=«Не изоморфизм», тогда выполнить следующие шаги k раз.
3.1. Выработать случайный бит b.
3.2. Если b=1, тогда
3.2.1. Сгенерировать случайную перестановку G¢
графа G.
3.2.2. Вычислить P(G,G¢).
3.2.3. Если P(G,G¢)=«Не изоморфизм», тогда подать на выход «Сбой».
3.3. Если b=0, тогда
3.3.1. Сгенерировать случайную перестановку H¢
графа H.
3.3.2 Вычислить P(G,H¢).
3.4. Если P(G,H¢)=«Изоморфизм», тогда подать на выход «Сбой».
4. Подать на выход «Норма».