МЕНЮ

Каталог

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

 

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

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

Общий вход: $ p$ и $ q$ - простые числа, $ y, g_1 , g_2 , ..., g_k in G_q$. 

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

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

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

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

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

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

 

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

 
Ссылки
  • D. Chaum, J.-H. Evertse, & J. van de Graaf, “An Improved Protocol for Demonstrating Possession of a Discrete Logarithm and Some Generalizations”, Advances in Cryptology EUROCRYPT '87, D. Chaum & W.L. Price (Eds.), Springer-Verlag, pp. 127-141.
  • Запечников С.В. Криптографические протоколы и их применение в финансовой и коммерческой деятельности: Учебное пособие для вузов. - М.: Горячая линия - Телеком, 2007. - 320с. - С.31