Zero-knowledge proof

[catpad]

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

Comments

[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. А что, если ...
Хотя и симпатично.