МЕНЮ

Каталог

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

 

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

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

Общий вход: граф $ G=(V,E)$. 

1) Первый шаг доказывающего. Пусть $ psi$ - $ 3$-раскраска графа $ G$. Доказывающий выбирает случайную перестановку $ pi$ множества $ {1,2,3}$ и устанавливает$ varphi(v)=pi(psi(v))$ для каждого $ vin V$. Следовательно, доказывающий образовывает случайную перемаркировку $ 3$-раскраски $ psi$. Доказывающий отправляет проверяющему последовательность из $ vert Vvert$ закрытых и непрозрачных ящиков таких, что $ v$-ый ящик содержит значение $ varphi(v)$. 

2) Первый шаг проверяющего. Проверяющий равномерно выбирает ребро $ (u,v)in E$ и отправляет его доказывающему. 

Примечание. Проверяющий просит проверить цвета вершин $ u$ и $ v$. 

3) Второй шаг доказывающего. Доказывающий отправляет проверяющему ключи от ящиков $ u$ и $ v$. 

4) Второй шаг проверяющего. Проверяющий открывает ящики $ u$ и $ v$ и принимает доказательство если и только если они содержат два различных элемента из $ {1,2,3}$. 

Общий вход: $ 3$-раскрашенный граф $ G=(V,E)$. Пусть $ n=vert V vert$ и $ V={1,2,...,n}$. 

Дополнительный вход доказывающего: $ 3$-раскраска графа $ G$, обозначаемая $ psi$. 

1) Первый шаг доказывающего. Пусть $ psi$ - $ 3$-раскраска графа $ G$. Доказывающий выбирает случайную перестановку $ pi$ множества $ {1,2,3}$ и устанавливает$ varphi(v)=pi(psi(v))$ для каждого $ vin V$. Доказывающий использует протокол привязки к биту для привязки собственно к цветам каждого из вершин. Т.е. доказывающий равномерно и независимо выбирает $ s_1,s_2,...,s_n in {0,1}^n$, вычисляет $ c_i = C_{s_i}(varphi(i))$для каждого $ i in V$ и отправляет $ c_1,c_2,...,c_n$ проверяющему. 

2) Первый шаг проверяющего. Проверяющий равномерно выбирает ребро $ (u,v)in E$ и отправляет его доказывающему. 

3) Второй шаг доказывающего. Без потери общности мы можем предположить, что сообщение, полученное от проверяющего, это ребро, обозначеное $ (u,v)$. (В противном случае, доказываюший задает $ (u,v)$ для некоторого заранее определенного ребра графа $ G$). Доказывающий использует (канонический) этап раскрытия протокола привязки к биту для того, чтобы раскрыть цвета вершин $ u$ и $ v$ проверяющему. 

4) Второй шаг проверяющего. Проверяющий проверяет правильно ли или неправильно были раскрыты значения, соответствующие $ u$ и $ v$, и являются ли они различными или нет. Т.е. после получения $ (s,sigma)$ и  проверяющий проверяет выполняются ли или нет следующие условия: $ c_u=C_s(sigma)$,  и $ sigma eq au$ (и $ sigma$ и $ au$ принадлежат $ {1,2,3}$). Если все условия выполняются, то проверяющий принимает доказательство. В противном случае, отвергает.

 

Основные сведения

 
Ссылки
  • O.Goldreich, S.Micali, A.Wigderson. How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design (extended abstract). In A.M. Odlyzko,editor,Advances in Cryptology|CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 171-185. Springer-Verlag, 1987, 11-15 August 1986