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

Доведення з нульовим розголошенням (англ. zero-knowledge proof, zero-knowledge protocol) — метод для доведення однією стороною іншій, що твердження (зазвичай — математичне) — істинне, без розкриття будь-якої іншої інформації, окрім достовірності твердження.

Абстрактні приклад

Печера Алі-Баби

Оксана випадковим чином обирає вхід A чи B, тоді як Тарас чекає зовні

Тарас обирає вихід, через який має вийти Оксана, і називає його Оксані

Оксана виходить через вихід названий Тарасом

Історію, що показує деякі ідеї доведення з нульовим розголошенням, вперше оприлюднили Жан-Жак Квісквотер та ін. в їх роботі «Як пояснити протокол нульового розголошення вашим дітям». На кшталт Аліси й Боба в криптографії в англомовних версіях доведення з нульовим розголошенням використовують Пеґґі (англ. Peggy — мнемоніка для англ. Prover), який доводить твердження, і Віктора (англ. Victor — мнемоніка для англ. Verifier), який перевіряє твердження. У нас — Оксана і Тарас^[].

У цій історії Оксана виявила таємне слово, що відкриває секретні двері в печері. Печера утворена у вигляді кола, з входом з одного боку та магічними дверима, що закривають інший бік проходу. Тарас каже, що заплатить за секрет, як впевниться, що Оксана справді знає його. Оксана каже, що скаже секрет лише після оплати. Вони розробили схему, за якої Оксана може довести Тарасові своє знання, не кажучи йому секретного слова.

Спочатку Тарас очікує зовні печери, Оксана входить. Вони позначили лівий та правий проходи як A і B. Тоді Тарас заходить у печеру і вигукує назву проходу, яким має вийти Оксана. Якщо вона справді знає магічне слово, то для неї легко вийти будь-яким проходом. Зауважте, Тарас не знає, яким саме проходом Оксана ввійшла.

Уявімо, що вона не знає слова. Тоді вона зможе вийти лише через той прохід, яким вона увійшла, тобто, ймовірність вийти названим Тарасом проходом у неї 50 відсотків. Якщо повторити, припустимо, 20 разів підряд, шанси Оксани постійно вгадувати назву проходу, що назве Тарас, надзвичайно малі (${\displaystyle {\frac {1}{2^{20}}}\approx {\frac {1}{1\ 000\ 000}}}$).

Отже, якщо Оксана впевнено з'являється з того виходу, який обирає Тарас, він може переконатись, що вона, швидше за все, знає таємне слово.

Дві кульки і друг, що не розрізняє кольорів

Уявіть собі друга, який не розрізняє червоний і зелений, а ви розрізняєте і у вас є дві кульки: одна червона і ще одна зелена, однакові за всіма іншими ознаками. Для вашого друга вони видаються геть однаковими і він сумнівається, що їх насправді можна відрізнити. Ви хочете довести йому, що вони мають різний колір, але нічого окрім цього; зокрема, ви не хочете видати яка з них якого кольору.

Ось підхід до доведення. Ви даєте ці кульки другові і він ховає за спиною. Далі, він показує вам одну з кульок. Він знов ховає її за спиною і потім знов показує вам одну кульку, обираючи будь-яку з них з однаковою ймовірністю. Він запитує вас, «Чи поміняв я кульку?» Процедуру можна повторити за необхідності.

Звісно, побачивши її колір ви можете впевнено сказати чи поміняв він їх. З іншого боку, якби вони були однакового кольору, то ви б не могли цього сказати з імовірністю більш ніж 50 %.

Через те, що імовірність випадкового успіху становить 50 %, імовірність випадково правильно відповісти в кількох спробах наближається до нуля.

Це доведення з нульовим розголошенням, бо ваш друг ніколи не з'ясує яка з кульок червона, а яка зелена.

Визначення

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

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. Нульове розголошення: якщо твердження істинне, жоден перевіряльник, який грає не за правилами, не може дізнатись нічого, окрім факту істинності.

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

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

Доведення з нульовим розголошенням не є доведенням в математичному сенсі, бо існує мала ймовірність (англ. 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).}$

Де ${\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}}}$ і симулятора обчислювально нерозрізненні, при одному допоміжному рядку.

Приклад з ізоморфізмом графів

Розглянемо приклад системи доведення з нульовим розголошенням для ізоморфізму графів. Маємо два графи ${\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}$.

Див. також

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

Примітки

1. Наведене формальне визначення подане за Goldwasser, Micali і Rackoff, 1985

Джерела

1. Quisquater Jean-Jacques. How to Explain Zero-Knowledge Protocols to Your Children. — 1990. — Т. 435. — С. 628–631.
2. Кулага, 2011, Основні визначення.
3. Igor Gorodezky (26 березня 2009). (PDF). Theory of Computing. Корнелльський університет. Архів оригіналу (PDF) за 18 червня 2012. Процитовано 6 червня 2012.
4. Kevin Snow (39.01.2007). (PDF). 600.641 Special Topics in Theoretical Cryptography. Університет Джонса Гопкінса. Архів оригіналу (PDF) за 16 березня 2014. Процитовано 6 червня 2012.

Посилання

• Кулага А. А. Протокол доведення знання розв'язку задачі Діффі–Хеллмана з нульовим розголошенням // НАУКОВІ ЗАПИСКИ НаУКМА. — 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.