Zero-knowledge proof

[catpad]

Наконец-то узнал, что такое zero-knowledge proof. Удивительная вещь ! Можно абсолютно точно доказать кому-то, что ты кое-что знаешь наверняка, никак при этом не открывая своего знания. Причём тот, кого убеждают, может сам выбирать, насколько он хочет быть уверенным в подлинности доказательства, то есть варьировать степень своей уверенности.
Вот это да.

Comments

[mopexod.livejournal.com]

Это как ?!

[catpad.livejournal.com]

На самом деле очень просто !
Если б я поступил честно, то сразу и написал бы суть дела. Но мне было лень.
И не только - когда узнаешь, в чём дело, теряется вся прелесть этого волнующего откровения.
Ну да ладно, напишу.

Возьмем какую-нибудь NP-complete задачу. Например, о трёхцветном раскрашивании графа, т.е., чтобы никакие две смежные вершины не были одинакового цвета.
Допустим, А говорит: я эту задачу решил (то есть "доказал", что для данного графа решение существует). В говорит: ну-ка докажи !
Тогда А втайне раскрашивает вершины графа и чем-нибудь их закрывает. В говорит - открывай вот эти две смежные вершины. А открывает - они закрашены разными цветами. "Сойдёт ?" - спрашивает А. "Не тут-то было", - отвечает В - "давай другие две".
А раскрашивает вершины другими цветами (или просто перемешивает те же самые), закрывает и по указке В снова открывает любые две смежные - они опять разного цвета.
И так продолжается, пока В не удовлетворит своих аппетитов.
Легко подсчитать, что, если В в начале на 100% уверен, что А лжёт, то после первого раунда его уверенность становится (N-1)/N (N - число вершин), после второго (N-1)/N в квадрате и т.д., до бесконечности. Как понятно, очень быстро вероятность вранья А падает почти до нуля, причем В сам выбирает точность, но при этом не узнаёт, как на самом деле раскрашен граф.
Красиво.

[gianthare.livejournal.com]

Непонятно. Что мешает А каждый раз выдавать два случайных разных цвета?

[catpad.livejournal.com]

Что значит "выдавать случайные цвета" ? Он уже раскрасил и не знает, какие вершины попросит его открыть В.

[mopexod.livejournal.com]

Постой-ка, а как А убеждает В в том, что он умеет раскрашивать больше, чем по две вершины? Может он (зараза!) только по две и умеет и красит их в два разных цвета каждый раз перед тем, как В смотрит! И даже,если В смотрит не по две, а по К - это не должно убеждать его в правдивости А - ведь может быть А умеет красить только по К или меньше.
Или В придётся проглядеть все вершины - но тогда он узнает всё!

[catpad.livejournal.com]

Так дело же в том, что он не знает, какие именно вершины попросит его открыть В ! Пусть он красит только по две, но с большой вероятностью В его разоблачит уже в первом раунде. К тому же, сам В выбирает количество раундов.

[mopexod.livejournal.com]

А разве "А" не может их красить прямо перед открытием? Он ведь сам их открывает? Или "В" их сам открывает - тогда почему он должен ограничивать себя парами?

[catpad.livejournal.com]

Ты просто неправильно подходишь к этой штуке. Ты ее рассматриваешь как некое противоборство сторон или игру с надувательством, а на самом деле это "честная" игра по строго определённым правилам. А не хитрит, а В имеет право открыть только две вершины - считай, что они автоматы. Этот пример - просто некая иллюстрация к теоретическому обоснованию, больше ничего.

[mopexod.livejournal.com]

Понятно. Пример Винарского прояснил ситуацию.
А вообще очень интересная тема, спасибо!

[senbu.livejournal.com]

Психология в картинках ;)