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]

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

Оффтопик

[khatul.livejournal.com]

Кэтпэд-сан, извини! Я прошу разрешения на выход из достославного проекта котокниги за неимением времени. Продолжайте с моим МРЯУсловением!

Подарок напоследок:

НЭКО-СЭНРЮ

Сколько вас, котов!
И не счесть ваших ушей,
лапок и хвостов!

(28 ноября 2002)

ФЕЛИСИТÀ

Мы, Царь Природы Божьей милостью,
На вашем стуле восседающий,
Решили, что Нам нужно вырасти,
А значит, Нам нужна еда еще.

Чтоб стал пушистей и объемистей
Наш организм всепоглощающий,
Извольте мясо и бульон нести,
Готовьте масло и леща еще.

Поев, Мы заурчим пленительно,
Мы станем по столу расхаживать,
И, может быть, позволим Нашему

Придворному телохранителю
животик тепленький поглаживать
Царю Земли - Коту Домашнему!

(а это - старое, около 1999)

О КОШКЕ В ОКОШКЕ

О чем рыдает мурка та?
- Ах, дайте, дайте мне кота!
Сегодня мне неможется -
Так хочется размножиться!

(11 января 1999)

На правах координатора ненавязчиво поинтересуюсь:

[bdbd.livejournal.com]

а, может, всё-таки время от времени?

Re: Оффтопик

[catpad.livejournal.com]

Спасибо, Хатуль-сан, и это в дело пойдет.
Очень жаль, что не можешь участвовать. Но присоединюсь к bdbd: можно ведь и время от времени, и даже после конкурса.

[ex-ilyavinar899.livejournal.com]

Классический пример:

ilyavinarsky: я знаю, что эти две пещеры между собой сообщаются, но не скажу тебе, как.

catpad: докажи.

ilyavinarsky заходит в первую пещеру, и выходит из второй.

catpad: а может, это вышел твой брат-близнец?

ilyavinarsky: дай мне что-нибудь; я зайду и выйду с ним.

catpad дает ilyavinarsky фонарик. ilyavinarsky заходит с ним в первую пещеру, и выходит с ним из второй.

catpad: а может, у вас там склад фонариков, и твой близнец тебе по радио передал взять фонарик?

ilyavinarsky: ну, дай мне что-нибудь еще.

Вероятность того, что во второй пещере есть склад всего, что catpad выбрал, стремительно падает до ноля. catpad убеждается в том, что ilyavinarsky действительно знает проход между пещерами - но не знает абсолютно ничего об этом проходе.

[gianthare.livejournal.com]

.

[avva.livejournal.com]

Но абсолютной уверенности всё равно нет - только относительная, стремящаяся к 1 в пределе.

[nine_k]

Можно протащить сквозь проход оптоволокно :-) При желании -- воспользоваться квантовой "подписью", чтобы убедиться, что проходящие по нему сообщение не перехватываются и кабель не имеет разрывов.

[30x40.livejournal.com]

А если наблюдать непрерывно за входом и в первую пещеру и во вторую - также вероятность того, что у ilyavinarsky есть N близнецов, сидящих во второй пещере :-)

[catpad.livejournal.com]

А что, если у него там подземный ход, ведущий на опушку леса, где его ждёт гоночный автомобиль ? Он едет до ближайшего города, покупает необходимую вещь и даёт её очередному брату близнецу.

[khatul.livejournal.com]

А это как раз будет означать, что пещеры сообщаются (через 2 подз. хода).

[catpad.livejournal.com]

Это я к тому, что всякие real-world examples "загрязнены" помехами этого самого real world. А что, если ...
Хотя и симпатично.