МЕНЮ

Каталог

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

 

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

Пусть $ N$ - множество натуральных чисел, $ n in N$ и $ Z_n^* = {xvert 1leq x < n, (n,x)=1}$множество натуральных чисел, меньших чем $ n$ и взаимно простых с $ n$. $ x in Z_n^*$ называется квадратичным вычетом по модулю $ n$, если существует такой $ y$, что $ y^2 equiv xpmod n$. В противном случае, $ x in Z_n^*$ называется квадратичным невычетом по модулю $ n$. 

Пусть $ n in N$ и $ x in Z_n^*$. Пусть $ P$ знает такой $ y$, что $ y^2 equiv xpmod n$. $ P$ хочет доказать $ V$свое знание, не показывая сам $ y$.
Описание протокола

Общий вход: натуральные числа $ n$ и $ x$ в двоичном представлении, $ x in Z_n^*$, $ vert xvert=m$. 

1) Первый шаг доказывающего. Используя случайные биты, $ P$ генерирует $ u$, случайный квадратичный вычет по модулю $ n$, и отправляет его проверяющему. 

2) Первый шаг проверяющего. $ V$ получает $ u$. $ V$ проверяет выполняется ли $ u in Z_n^*$, если нет, то он останавливается. $ V$ генерирует случайный бит $ alpha$ и отправляет его доказывающему. 

3) Второй шаг доказывающего. $ P$ получает $ alpha$. Если $ alpha=0$, то $ P$ использует случайные биты и генерирует $ v$, случайный квадратный корень из $ u$ по модулю $ n$, если $ alpha=1$, то $ P$ использует случайные биты и генерирует $ v$, случайный квадратный корень из $ ux$ по модулю $ n$. $ P$ отравляет $ v$ проверяющему. 

4) Второй шаг проверяющего. $ V$ получает $ v$. $ V$ проверяет выполняется ли $ v in Z_n^*$ и или$ alpha=0$ и $ v^2pmod n$ $ =u$, или $ alpha=1$ и $ v^2pmod n$ $ =(ux)pmod n$, если нет, то он останавливается. 

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

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

 

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

Shafrira GoldwasserSilvio MicaliCharles Rackoff

 
Ссылки
  • S.Goldwasser, S.Micali and C.Rackoff. The Knowledge Complexity of Interactive Proof System. SIAM Journal on Computing, Vol.18, pages 186-208, 1989
  • Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. - С.698-700