МЕНЮ

Каталог

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

 

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

Пусть $ p$ и $ q$ - простые числа такие, что $ qvert (p-1)$, пусть $ gin Z^*_p$ и $ X$ - число. Пусть $ P$ знает $ xin Z_q$ такой, что $ g^x = X$. $ P$ хочет доказать $ V$ свое знание, не показывая сам $ x$.
Описание протокола

Общий вход: $ p$ и $ q$ - простые числа такие, что $ qvert (p-1)$, $ gin Z^*_p$ и $ X$ - число. 

1) Первый шаг доказывающего. $ P$ выбирает наугад $ rin Z_q$ и вычисляет$ hequiv g^r pmod p$. $ P$ отправляет $ h$ проверяющему. 

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

3) Второй шаг доказывающего. $ P$ вычисляет $ kequiv r+xb pmod q$ и отправляет его проверяющему. 

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ g^kequiv X^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с. - С.30-31