об обедающих криптографах
Dec. 14th, 2003 06:05 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПрочитал об алгоритме обедающих криптографов. Понравилось — остроумно! Перескажу.
Предположим, трое криптографов пришли в какой-то ресторан пообедать. После того, как они уселись за стол, официант сообщает им, что их обед оплатил заранее некий анонимный доброжелатель.
Криптографы знают, что этим доброжелателем мог быть один из них, но, кроме того, им мог быть некий внешний орган (определённости ради предположим, что этим внешним органом может быть только NSA, федеральное агентство национальной безопасности США, очень интересующееся криптографией и криптографами). Они хотят выяснить, действительно ли заплатил за обед один из них, или это дело рук NSA. Но при этом они очень тактичны, так что, если заплатил один из них, они не хотят, чтобы другие двое об этом узнали. Поэтому они не могут, скажем, просто договориться, что тот из них, кто заплатил (если есть такой), признается в этом.
Могут ли они выяснить, заплатил ли один из них, не выдавая при этом самим себе информацию о том, кто именно? Оказывается, могут, и вот как.
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой) говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Простое задание: докажите, что этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно. Это несложно и занимательно. Для тех, у кого не получается или лень думать, объяснение:
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или NSA.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатило NSA, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
По-моему, очень красиво. Этот алгоритм придумал David Chaum и опубликовал в 1988-м году в статье The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, которая есть в сети (см. ссылку).
Предположим, трое криптографов пришли в какой-то ресторан пообедать. После того, как они уселись за стол, официант сообщает им, что их обед оплатил заранее некий анонимный доброжелатель.
Криптографы знают, что этим доброжелателем мог быть один из них, но, кроме того, им мог быть некий внешний орган (определённости ради предположим, что этим внешним органом может быть только NSA, федеральное агентство национальной безопасности США, очень интересующееся криптографией и криптографами). Они хотят выяснить, действительно ли заплатил за обед один из них, или это дело рук NSA. Но при этом они очень тактичны, так что, если заплатил один из них, они не хотят, чтобы другие двое об этом узнали. Поэтому они не могут, скажем, просто договориться, что тот из них, кто заплатил (если есть такой), признается в этом.
Могут ли они выяснить, заплатил ли один из них, не выдавая при этом самим себе информацию о том, кто именно? Оказывается, могут, и вот как.
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой) говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Простое задание: докажите, что этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно. Это несложно и занимательно. Для тех, у кого не получается или лень думать, объяснение:
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или NSA.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатило NSA, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
По-моему, очень красиво. Этот алгоритм придумал David Chaum и опубликовал в 1988-м году в статье The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, которая есть в сети (см. ссылку).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
no subject
Date: 2003-12-13 08:51 pm (UTC)no subject
no subject
Date: 2003-12-13 10:46 pm (UTC)а если платил 10.
Но тогда вы не криптограф, а скучный обыватель
no subject
Date: 2003-12-13 10:52 pm (UTC)в приниципе traceable. Остается возможнось отследить кто какую монету положил. То есть в системе сохранена информация, кто именно платил.
А у аввы - вроде нет
no subject
Date: 2003-12-13 11:03 pm (UTC)но и безумно любопытны, и будут стараться любой ценой выяснить кто именно платил. В противном случае, как заметил ipain можно просто каждому шепнуть на ухо официанту, платил он или нет и попросить официанта сказать в конце был ли источник внешним.
no subject
Date: 2003-12-14 03:01 am (UTC)Или "ноль"
no subject
Date: 2003-12-14 03:02 am (UTC)Это будет мой первый мемориес :)
Date: 2003-12-14 03:03 am (UTC)no subject
Date: 2003-12-14 07:17 am (UTC)no subject
Date: 2003-12-14 07:31 am (UTC)no subject
Date: 2003-12-14 08:22 am (UTC)но типа можно и без монеток? первый говорит второму -
одинаковые (или разные); второй повторяет слово третьему
или (если платил) меняет его на противоположное.
третий по тем же правилам сообщяет слово первому.
первый обьявляет результат.
любят нескучные криптографы монетки без смысла кидать.
no subject
Date: 2003-12-14 10:52 am (UTC)скaжем 1й придумывaет "одинaковые" и говорит второму. Второй зaплaтил, поэтому он меняет нa "рaзные." Третий не плaтил, но хочет узнaть, плaтил ли второй и меняет нa "одинaковые" опять. Первый получaет обрaтно и говорит "зaплaтило NSA," тогдa третий знaет, что зaплaтил второй.
Конечно, это не стопроцентно рaботaет -- если зaплaтил первый, то он очень удивится, и узнaет, что один из них соврaл. Если второй не плaтил, то первый подумaет, что кто-то зaплaтил и обьявит "зaплaтил кто-то из нaс.." и т.д., но все рaвно у третьего окaзывaется больше информaции, чем у других.
В aлгоритме
Похожий случай бал в Одессе
Date: 2003-12-14 10:57 am (UTC)Сотрудников выстроили в шеренгу и одели на головы шляпы разных цветов (число цветов - N). Каждый видит стоящих перед ним, но себя и стоящих сзади не видит.
Каждый слышит всех. Сотрудник должен произнести правильно цвет своей шляпы, тогда его не уволят. Как им поступить, чтобы сокращение было минимальным?
no subject
Date: 2003-12-14 11:21 am (UTC)ко всем трем ответам (хоть на мгновениеби хоть неизвестно какой ответ чей). В этом случае кодировка не лучше чем traceability ответов.
Официант может расколоться за рубль, все три монетки (в шапке или
под салфеткой) могут быть сфотографированы сверхчуствительным аппаратом способным выявить отпечатки пальцев (или утащены для анализа) и т.д.
Грубо говоря хочется чтобы по условию предполагалось что все
возможные способы будут задействованны (иначе участники могут просто договориться не применять какие-то дешифровальные методы)
no subject
Date: 2003-12-14 11:34 am (UTC)Суть в том что если кому то известны все три ответа (в любой форме)
то крепкость кодировки ограничена тем, насколько легко распознать какой ответ кому принадлежит. То есть задача еще не решена стопроцентно, пока не придумано как сделать ответы untraceable.
Монетки в шапке лучше, чем просто все выложить четвертому доверенному лицу, но логически эквивалентны
Д.
Но Вы правы - нет чтоб криптографы просто порадовались бесплатному обеду !
Re: Похожий случай бал в Одессе
Date: 2003-12-14 04:17 pm (UTC)Сдаюсь, расскажите ;)
Re: Похожий случай бал в Одессе
Date: 2003-12-14 05:01 pm (UTC)http://www.livejournal.com/users/igorlord/3781.html
Re: Похожий случай бал в Одессе
Date: 2003-12-14 05:04 pm (UTC)no subject
Date: 2003-12-14 11:10 pm (UTC)Re: Похожий случай был в Одессе
Date: 2003-12-15 04:43 am (UTC)Первым говорит тот, кто видит всех (кроме себя). Он говорит коллегам их "контрольную сумму", т.е. сумму по модулю N.
Каждый следующий:
слышал тех, кто высказался сзади,
видит тех, кто стоит впереди,
знает контрольную сумму и...
без проблем называет свой цвет.
Ответ: Уволят только первого. С вероятностью 1/N цвет его шляпы совпадёт с контрольной суммой, тогда спасутся все.