Zero-knowledge proof

[catpad]

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

Comments

[mopexod.livejournal.com]

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

[catpad.livejournal.com]

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

[mopexod.livejournal.com]

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

[catpad.livejournal.com]

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

[mopexod.livejournal.com]

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