МЕНЮ

Каталог

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

 

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

Пусть $ 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$.

Пусть $ a$ — целое число, и $ p$ — простое число, отличное от $ 2$. Символ Лежандра $ left(frac{a}{p} ight)$определяется следующим образом:

$ left(frac{a}{p} ight)=0$, если $ a$ делится на $ p$;

$ left(frac{a}{p} ight)=1$, если $ a$ является квадратичным вычетом по модулю $ p$, то есть $ a$ не делится на $ p$ и существует такое целое $ b$, что $ b^2equiv apmod p$;

$ left(frac{a}{p} ight)=-1$, если $ a$ является квадратичным невычетом по модулю $ p$, то есть $ a$ не делится на p и не является квадратичным вычетом по модулю $ p$.

Пусть $ P$ — нечётное, большее единицы число и $ P=p_1p_2ldots p_n$ — его разложение на простые множители (среди $ p_1,;ldots,;p_n$ могут быть равные). Тогда для произвольного целого числа $ a$ символ Якоби определяется равенством:

$ left(frac{a}{P} ight)=left(frac{a}{p_1} ight)left(frac{a}{p_2} ight)cdotsleft(frac{a}{p_n} ight)$,

где $ left(frac{a}{p_i} ight)$ — символы Лежандра.

По определению считаем, что $ left(frac{a}{1} ight)=1$ для всех $ a$.

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

Общий вход: натуральные числа $ n$ и $ x$ в двоичном представлении, $ x in Z_n^*$ $ left(frac{x}{n} ight)=1 $,$ vert xvert=m$, $ m=log_2 n$ 

1) Первый шаг проверяющего. Используя случайные биты, $ V$ выбирает наугад $ r_0 in Z_n^*$ и бит $ alpha in {{0,1}}$. Если $ alpha=0$, то $ V$ задает $ wequiv r_0^2pmod m$, если же $ alpha=0$, то $ V$задает $ wequiv xcdot r_0^2pmod m$. $ V$ отправляет $ w$ доказывающему. Затем $ V$ выбирает два случайных множества, каждое мощности $ m$

 

$displaystyle T={t_i vert t_iequiv r_i^2 pmod n,; i=1,...,m}$

 

и

 

$displaystyle S={t_i vert t_iequiv xcdot r_i^2 pmod n,; i=1,...,m}.$

 

$ V$ отправляет доказывающему $ P$ элементы множества $ Tcup S$ в случайном порядке. 

2) Первый шаг доказывающего. $ P$ выбирает случайное подмножество $ Z subseteq Tcup S$мощности $ m$ и отправляет его обратно проверяющему. 

3) Второй шаг проверяющего. Для каждого $ z in Z$ $ V$ отправляет доказывающему $ P$ $ r$такой, что $ zequiv r^2pmod n$ или $ zequiv xcdot r^2pmod n$. Пусть разность мощностей множеств $ T-Z$ и $ S-Z$ равна $ d$. Тогда $ V$ выбирает $ d$ случайных элементов$ t_{i_1},...,t_{i_d}$ из большего множества и отправляет их соответствующих $ r_{i_1},...,r_{i_d}$доказывающему $ P$ (т.е. $ t_{i_j}equiv r_{i_j}^2 pmod n$ или $ t_{i_j}equiv xcdot r_{i_j}^2 pmod n$ для некоторых$ 1leq i_j leq 2n$). $ V$ задает $ X=T-Z-{t_{i_1},...,t_{i_d}}$ и $ Y=S-Z-{t_{i_1},...,t_{i_d}}$. Если$ wequiv r_0^2pmod n$ $ V$ полагает

 

 

 

 

а если $ wequiv xcdot r_0^2pmod n$, то $ V$ полагает

 

 

 

 

$ V$ отправляет элементы множества  в случайном порядке. 

4) Второй шаг доказывающего. $ P$ проверяет, что  такого вида как в 3) (т.е. для всех  $ v^2equiv t_icdot w pmod n$ или $ v^2equiv t_icdot wcdot x pmod n$ для некоторого$ t_i in Xcup Y$) и что . Если это не так, то $ P$ останавливается, обнаруживая обман. В противном случае, $ P$ отправляет $ V$ значение $ eta=Q_n(w)$. 

5) $ V$ проверяет значение $ eta=Q_n(w)$. Если $ eta eqalpha$, то останавливается, обнаруживая обман. 

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

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

 

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

Shafrira GoldwasserSilvio MicaliCharles Rackoff

 
Ссылки
  • S.Goldwasser, S.Micali and C.Rackoff. The Knowledge Complexity of Interactive Proof System. In Proceeding of 17th ACM Symposium on the Theory of Computing, pages 291-304, 1985
  • 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 с. - С.700