Прочитал об алгоритме обедающих криптографов. Понравилось — остроумно! Перескажу.
Предположим, трое криптографов пришли в какой-то ресторан пообедать. После того, как они уселись за стол, официант сообщает им, что их обед оплатил заранее некий анонимный доброжелатель.
Криптографы знают, что этим доброжелателем мог быть один из них, но, кроме того, им мог быть некий внешний орган (определённости ради предположим, что этим внешним органом может быть только NSA, федеральное агентство национальной безопасности США, очень интересующееся криптографией и криптографами). Они хотят выяснить, действительно ли заплатил за обед один из них, или это дело рук NSA. Но при этом они очень тактичны, так что, если заплатил один из них, они не хотят, чтобы другие двое об этом узнали. Поэтому они не могут, скажем, просто договориться, что тот из них, кто заплатил (если есть такой), признается в этом.
Могут ли они выяснить, заплатил ли один из них, не выдавая при этом самим себе информацию о том, кто именно? Оказывается, могут, и вот как.
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой)
говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Простое задание: докажите, что этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно. Это несложно и занимательно. Для тех, у кого не получается или лень думать, объяснение:
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или NSA.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатило NSA, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
По-моему, очень красиво. Этот алгоритм придумал David Chaum и опубликовал в 1988-м году в статье The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability.
http://avva.livejournal.com/1035705.html
