МЕНЮ

Каталог

ДОКАЗАТЕЛЬСТВО ЗНАНИЯ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВА ЧИСЕЛ В СООТВЕТСТВУЮЩИХ БАЗИСАХ Протокол SNB
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

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

Пусть $ p$ и $ q$ простые числа, пусть $ y^{(j)}, g_1^{(j)} , g_2^{(j)} , ..., g_k^{(j)} in G_q$ для некоторых $ j$. Пусть $ P$знает $ alpha_1 , alpha_2 , ..., alpha_k in Z_q$ такие, что для любого $ j$ $ y^{(j)} = {(g_1^{(j)})}^{alpha_1}cdot {(g_2^{(j)})}^{alpha_2}cdot ... cdot {(g_k^{(j)})}^{alpha_k}$. $ P$ хочет доказать $ V$ свое знание, не показывая сами $ alpha_1 , alpha_2 , ..., alpha_k$. 
Описание протокола

Общий вход: $ p$ и $ q$ - простые числа, $ y^{(j)}, g_1^{(j)} , g_2^{(j)} , ..., g_k^{(j)} in G_q$ для некоторых $ j$. 

1) Первый шаг доказывающего. $ P$ выбирает наугад $ r_1, r_2, ..., r_n in Z_q$ и вычисляет для каждого $ j$ $ h^{(j)}equiv (g_1^{(j)})^{r_1}cdot (g_2^{(j)})^{r_2}cdot ... (g_n^{(j)})^{r_n} pmod p$. $ P$ отправляет $ h^{(j)}$проверяющему. 

2) Первый шаг проверяющего. $ V$ выбирает наугад $ bin {0,1}$ и отправляет его доказывающему. 

3) Второй шаг доказывающего. $ P$ вычисляет $ k_i equiv r_{i}+alpha_{i} b pmod q$ $ i=1,2,...,n$ и отправляет его проверяющему. 

4) Второй шаг проверяющего. $ V$ проверяет для каждого $ j$ выполнение условия$ (g_1^{(j)})^{k_1}cdot (g_2^{(j)})^{k_2}cdot ... cdot (g_n^{(j)})^{k_n}equiv (y^{(j)})^bcdot h^{(j)} pmod p$. Если оно не выполняется, $ V$останавливает проверку и отвергает доказательство. 

5) $ P$ и $ V$ повторяют шаги 1) - 4) $ m$ раз. 

Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 4). В противном случае, отвергает. 

 

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

 
Ссылки
  • Запечников С.В. Криптографические протоколы и их применение в финансовой и коммерческой деятельности: Учебное пособие для вузов. - М.: Горячая линия - Телеком, 2007. - 320с. - С.31-32