暗号学者の晩餐問題

久々に面白い問題に出会った。それは以下の暗号学者の晩餐問題って呼ばれてるもんやった。
-------------------------------------------------------------------
　３人の暗号学者が夕飯をともにした。精算しようとするとすでに支払いは終わっていたという。３人の中の１人がこっそり好意で支払ってくれたのか、あるいは、（日ごろお世話になっている）NSA（国家安全保障局）が代わりに支払ってくれたかのどちらかである。匿名の支払者の粋な計らいを尊重したいが、もしも後者だったら嫌だ。そこで、次のプロトコルを実行した。
　まず３人の間にメニューを立てて、他から覗けないようにしてコインを投げる。Aは自分のコインと右隣のBのコインの結果を見て、その２つが「同じ」か「違う」かのどちらかを叫ぶ。ただし、もしも自分が支払っていなければ正直に答え、自分が支払っていれば逆を答える。これをBとCも繰り返す。３人の答えの内「違う」の数が奇数ならば３人の誰かが支払者、偶数ならばNSAが支払者である。
　メニューのおかげでそれぞれのコインの表裏はわからず、それ故に、誰が「うそ」をついているかもわからない。このプロトコルを１回実行することで匿名の送信者が１ビットの情報を送信していることになる。
----------------------------------------------------------------
かなり面白い問題やなーって久しぶりに感激した。
それにしても最近飲みすぎやな～俺。