МЕНЮ

Каталог

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

 

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

Пусть $ f$ - однонаправленная и гомоморфная функция над группой $ Z_n$, $ X=f(z)$ - для некоторого $ zin Z_n$. Пусть $ P$ знает элемент $ zin Z_n$, удовлетворяющий условию $ X=f(z)$. $ P$ хочет доказать $ V$ свое знание, не показывая сам элемент $ z$.
Описание протокола

Общий вход: $ f$ - однонаправленная и гомоморфная функция над группой $ Z_n$, $ X=f(z)$- для некоторого $ zin Z_n$. 

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

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

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

4) Второй шаг проверяющего. $ V$ проверяет выполнение условия $ f(r)=c$, если $ b=0$, или $ f(r)=c-X$, если $ b=1$. Если оно не выполняется, $ V$ останавливает проверку и отвергает доказательство. 

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

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

 

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

 
Ссылки
  • Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. - С.259, 679