МЕНЮ

Каталог

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

 

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

Пусть $ p$ и $ q$ - простые числа такие, что $ qvert p-1$, $ pgeq 2^{512}$, $ qgeq 2^{140}$. Пусть $ g in Z_n$, порядок по модулю $ p$ которого равен $ q$. Пусть $ y=g^{-z} pmod p$ для некоторого $ zin Z_q$. Пусть $ P$знает элемент $ zin Z_q$, удовлетворяющий условию $ yequiv g^{-z} pmod p$. $ P$ хочет доказать $ V$свое знание, не показывая сам элемент $ z$. 
Описание протокола

Общий вход: $ p$ и $ q$ - простые числа такие, что $ qvert p-1$, $ pgeq 2^{512}$, $ qgeq 2^{140}$, $ g in Z_n$, порядок по модулю $ p$ которого равен $ q$, $ y=g^{-z} pmod p$ для некоторого $ zin Z_q$. 

1) Первый шаг доказывающего. $ P$ выбирает случайным образом $ k in_U Z_n$ и вычисляет число $ c = g^k pmod p$. $ P$ отправляет $ c$ проверяющему. 

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

3) Второй шаг доказывающего. $ P$ получает $ b$. $ P$ вычисляет $ r = k+zbpmod p$ и отправляет его проверяющему. 

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ c=g^r y^b$. Если оно не выполняется, $ V$ останавливает проверку и отвергает доказательство. 

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

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

 

Основные сведения
Авторы

Claus-Peter Schnorr

 
Ссылки
  • Schnorr C.P. Efficient Identification and Signatures for Smart Cards. Advances in Cryptology - Crypto '89. Lecture Notes in Computer Science, Vol.435, Springer Verlag, pp.235-251, 1990.
  • Schnorr C.P. Efficient Signature Generation by Smart Cards. Journal of Cryptology, Vol.4, pp.161-174, 1991.
  • Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. - С.685-688