МЕНЮ

Каталог

ДОКАЗАТЕЛЬСТВО ИЗОМОРФИЗМА ГРАФОВ Протокол GI
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

Постановка задачи

Пусть $ P$ знает изоморфизм графов $ G_1$ и $ G_2$. $ P$ хочет доказать $ V$ свое знание, не показывая сам изоморфизм.
Описание протокола

Общий вход: пара графов $ G_1=(V_1,E_1)$ и $ G_2=(V_2,E_2)$. Пусть $ varphi$ - изоморфизм между$ G_1$ и $ G_2$, т.е. биективное отображение множества вершин $ V_1$ на множество вершин $ V_2$такое, что $ (u,v)in E_1$ тогда и только тогда, когда $ (varphi(u),varphi(v))in E_2$. 

1) Первый шаг доказывающего. Доказывающий $ P$ выбирает случайную изоморфную копию графа $ G_2$ и отправляет её проверяющему $ V$. Т.е доказывающий выбирает наугад перестановку $ pi$ из множества перестановок множества вершин $ V_2$ и строит граф с множеством вершин $ V_2$ и множеством ребер

 

$displaystyle F={(pi(u),pi(v)):(u,v)in E_2}.$

 

Доказывающий отправляет $ (V_2,F)$ проверяющему. 

Примечание. Если входные графы изоморфны, как утверждает доказывающий, то граф, отправленный на первом шаге изоморфен обоим входным графам. А если входные графы не изоморфны, то никакой граф не может быть изоморфным обоим входным графам. 

2) Первый шаг проверяющего. После получения графа  от доказывающего, проверяющий просит доказывающего показать изоморфизм между  и одним из входных графов, выбранным наугад проверяющим. А именно, проверяющий равномерно выбирает$ sigmain{1,2}$ и отправляет его доказывающему (который должен показать изоморфизм между $ G_sigma$ и ). 

3) Второй шаг доказывающего. Если сообщение, полученное от проверяющего, равно 2, то доказывающий отправляет $ pi$ проверяющему. В противном случае (т.е. если $ sigma eq 2$) доказывающий отправляет $ picircvarphi$ (т.е. композицию $ pi$ и $ varphi$, определенную как$ (picircvarphi)(v)=pi(varphi(v))$) проверяющему. (Примечание. Доказывающий рассматривает любой $ sigma eq 2$ как $ sigma=1$.) 

4) Второй шаг проверяющего. Если сообщение обозначаемое $ psi$, полученное от доказывающего, является изоморфизмом между $ G_sigma$ и , то проверяющий выдает 1 (т.е. принимает доказательство), в противном случае 0.