Доведення з нульовим розголошенням

Доведення з нульовим розголошенням повинно мати три властивості:

1. Повнота (англ. completeness): якщо твердження істинне, той хто чесно доводить (такий, що повністю слідує протоколу) завжди переконає чесного перевіряльника.

   ${\displaystyle \forall x\in L,Pr[\left(P,V\right)[x]=accept]\geq 1-negl\left(k\right).}$

2. Коректність (англ. soundness) захищає від прийняття хибного твердження: якщо твердження брехливе, то ймовірність обману V в будь-якому випадку має бути дуже низькою.

   ${\displaystyle \forall \notin L,\forall {\hat {P}},Pr[\left({\hat {P}},V\right)[x]=accept]\leq negl(k).}$

   ${\displaystyle {\hat {P}}}$ — імовірно зловмисний доводжувач.

3. Нульове розголошення: якщо твердження істинне, жоден перевіряльник, який грає не за правилами, не може дізнатись нічого, окрім факту істинності.

Зокрема, після того, як перевіряльник переконався в істинності твердження, сам він не зможе довести його істинність третім особам[2].

Дві перші властивості виконуються для загальної інтерактивної системи доведення. Третя властивість призводить до нульового розголошення.

Доведення з нульовим розголошенням не є доведенням в математичному сенсі, бо існує мала ймовірність (англ. soundness error) того, що нечесний доводжувач зможе переконати перевіряльника в істинності брехливого твердження. Інакше кажучи, доведення швидше ймовірнісне, ніж детерміністичне. Однак, наявні техніки зменшення можливості похибки до нехтовно малої.

Формальне визначення нульового розголошення потребує використання деякої обчислювальної моделі, найпоширеніше використання машини Тюрінга. Нехай ${\displaystyle P}$,${\displaystyle V}$ і ${\displaystyle S}$ будуть автоматами Тюрінга. Інтерактивна система доведення з ${\displaystyle (P,V)}$ для мови ${\displaystyle L}$ є з нульовим розголошенням, якщо для будь-якого перевіряльника ймовірнісно поліноміального часу (ІПЧ) (англ. probabilistic polynomial time (PPT)) ${\displaystyle {\hat {V}}}$ існує симулятор з очікуваним ІПЧ ${\displaystyle S}$, такий що

${\displaystyle \forall x\in L,z\in \{0,1\}^{*},View_{\hat {V}}[P(x)\leftrightarrow {\hat {V}}(x,z)]=S(x,z).}$[note 1][3]

Де ${\displaystyle View}$:

1. Розподіл імовірностей над ${\displaystyle P,V(x);}$ тобто, над всіма можливими перемовинами, що ${\displaystyle P}$ і ${\displaystyle V}$ можуть мати стосовно ${\displaystyle x,}$
2. ${\displaystyle View_{V}[P(x)\leftrightarrow V(x)]=<}$ повідомлення від ${\displaystyle P}$, випадковість ${\displaystyle V>.}$

Доводжувач ${\displaystyle P}$ змодельовано як такий, що має необмежену обчислювальну потужність (на практиці, P зазвичай є імовірнісною машиною Тюрінга). Інтуїтивно, визначення стверджує, що інтерактивна система доведення ${\displaystyle (P,V)}$ має нульове розголошення, якщо для будь-якого перевіряльника ${\displaystyle {\hat {V}}}$ існує дієвий симулятор ${\displaystyle S}$, який може відтворити розмову між ${\displaystyle P}$ і ${\displaystyle {\hat {V}}}$ на будь-якому вході. Отже, розмова з ${\displaystyle P}$ не може навчити ${\displaystyle {\hat {V}}}$ обчисленню чогось, чого він не міг обчислити до того.

Допоміжний рядок ${\displaystyle z}$ відіграє роль «попереднього знання» (англ. prior knowledge). Визначення має на увазі, що ${\displaystyle {\hat {V}}}$ не може використати якесь попереднє знання ${\displaystyle z}$, щоб отримати інформацію з розмови з ${\displaystyle P}$, бо ми вимагаємо, що якщо ${\displaystyle S}$ також має це знання, тоді він може відтворити перемовини між ${\displaystyle {\hat {V}}}$ і ${\displaystyle P}$ як і раніше.

Наведене визначення для ідеального нульового розголошення. Визначення обчислювального нульового розголошення отримаємо з вимогою, що погляди перевіряльника ${\displaystyle {\hat {V}}}$ і симулятора обчислювально нерозрізненні, при одному допоміжному рядку.

Розглянемо приклад системи доведення з нульовим розголошенням для ізоморфізму графів[4]. Маємо два графи ${\displaystyle G_{0}}$ і ${\displaystyle G_{1}}$, ${\displaystyle P}$ хоче переконати ${\displaystyle V}$, що знає перестановку ${\displaystyle \pi }$, таку що ${\displaystyle \pi \left(G_{0}\right)=G_{1}}$. ${\displaystyle P}$ може просто відіслати ${\displaystyle \pi }$ до ${\displaystyle V}$, але це не буде системою з нульовим розголошенням; треба переконати ${\displaystyle V}$, що ${\displaystyle \pi }$ це ізоморфізм, без розкриття будь-яких даних. Маємо наступний протокол:

• ${\displaystyle P\to V:P}$ випадковим чином обирає перестановку ${\displaystyle \sigma }$ і біт ${\displaystyle b\in \{0,1\}}$, обчислює ${\displaystyle H=\left(G_{b}\right)}$, і відсилає ${\displaystyle H}$ до ${\displaystyle V}$.
• ${\displaystyle V\to P:V}$ обирає біт ${\displaystyle b'\in \{0,1\}}$ і відправляє до ${\displaystyle P}$.
• ${\displaystyle P\to V:P}$ відправляє перестановку ${\displaystyle \tau }$ до ${\displaystyle V}$ , де

${\displaystyle {\begin{cases}\sigma ,&{\mbox{if }}b=b'\\\sigma \pi ^{-1},&{\mbox{if }}b=0,b'=1\\\sigma \pi ,&{\mbox{if }}b=1,b'=0\end{cases}}}$

• ${\displaystyle V}$ приймає тоді і лише тоді коли ${\displaystyle H=(G_{b'})}$.

Це протокол досконалої повноти, бо якщо це справді ізоморфізм, тоді завжди виконуватиметься ${\displaystyle \tau \left(G_{b'}\right)=\sigma \left(G_{b}\right)}$. Більше того, припустимо, що ${\displaystyle V}$ є чесним перевіряльником, який обирає ${\displaystyle b'}$ випадково. Отже, протокол також правильний, якщо ${\displaystyle \pi }$ не ізоморфізм, тоді ${\displaystyle \tau \left(G_{b'}\right)=\sigma \left(G_{b}\right)}$ лише в випадку ${\displaystyle b=b'}$, а це стається з імовірністю ${\displaystyle 1/2}$.

• Задача візантійських генералів — задача, вирішення якої призвело до побудови математичної моделі «доведення з нульовим розголошенням».
• Обман, здійсненний мафією — способи зловживання протоколами, в яких застосовується доведення з нульовим розголошенням.

• Кулага А. А. Протокол доведення знання розв'язку задачі Діффі–Хеллмана з нульовим розголошенням // НАУКОВІ ЗАПИСКИ НаУКМА. — 2011. — Т. 138 Комп’ютерні науки (15 листопада). — С. 19—24.
• О В Онацький, С М Горохов, О В Жарова. Криптографічний протокол доказу із нульовим розголошенням на еліптичних кривих // Наукові праці ОНАЗ ім. О.С. Попова. — Вип. 2. — С. 66—71.
• S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems // STOC ’85. — 1985. — P. 291—304.