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

       

Чекер для задачи «Изоморфизм графа»


Пусть 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. Подать на выход «Норма».



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