Доведення з нульовим пізнанням

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Абстрактний приклад[ред.ред. код]

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

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

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

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

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

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

Визначення[ред.ред. код]

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

  1. Повнота (англ. completeness): якщо твердження істинне, той хто чесно доводить (такий, що повністю слідує протоколу) завжди переконає чесного перевіряльника.
    \forall x \in L, Pr[\left(P, V\right)[x] = accept] \ge 1 - negl\left(k\right).
  2. Правильність (англ. soundness): якщо твердження брехливе, той хто доводить з обманом не може переконати чесного перевіряльника, що твердження істинне, можлива лише дуже мала ймовірність.
    \forall \notin L,  \forall \hat P, Pr[\left(\hat P, V\right)[x] = accept] \le negl(k).
    \hat P — імовірно зловмисний доводжувач.
  3. Нульове пізнання: якщо твердження істинне, жоден перевіряльник, який грає не за правилами, не може дізнатись щось окрім факту істинності.

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

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

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

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

Де View:

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

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

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

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

Приклад з ізоморфізмом графів[ред.ред. код]

Розглянемо приклад системи доведення з нульовим пізнанням для ізоморфізму графів. Маємо два графи G_0 і G_1, P хоче переконати V, що знає переставку \pi, таку що \pi\left( G_0\right)=G_1. P може просто відіслати \pi до V, але це не буде системою з нульовим пізнанням; треба переконати V, що \pi це ізоморфізм, без розкриття будь-яких даних. Маємо наступний протокол:

  • P \to V: P випадковим чином обирає переставку \sigma і біт b \in \{0, 1\}, обчислює H = \left(G_b\right), і відсилає H до V.
  • V \to P: V обирає біт b' \in \{0, 1\} і відправляє до P.
  • P \to V: P відправляє переставку \tau до V , де
\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}
  • V приймає тоді і лише тоді коли H = (G_{b'}).

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

Примітки[ред.ред. код]

  1. Quisquater Jean-Jacques How to Explain Zero-Knowledge Protocols to Your Children 435 (1990) С. 628–631.
  2. Наведене формальне визначення подане за Goldwasser, Micali і Racko

Джерела[ред.ред. код]