食事をする暗号学者 〜匿名性を守る投票の方法〜
- 2016-11-24 雑記帳
＃＃
10人の暗号学者に、「宝くじが当たったからご馳走をしたい」という招待状が、差出人不明で届いた。
10人は招待状に従って集まり、円卓で豪華な食事を堪能したのだが、招待状の差出人が誰なのかわからず、もやもやしていた。
招待状を送った主催者は正体を隠したいのであろうことは理解できるが、
この10人の中に主催者がいるのか、いないのか、それだけでも知りたいというのが全員の総意だった。
おそらく主催者本人も、正体をばらすことはせずとも、「10人の中にいること」自体は表明しても良いと思っているはずだ。
主催者がいるのか、いないのかを、主催者が誰かということが全く特定できない方法で明らかにする方法はあるだろうか？
＃＃
※「誰が主催者である可能性が高いか」ということすら見当がつかないような方法、つまり、「主催者がいるのか、いないのか」ただそれだけが情報としてわかる方法が求められています。
これは、「食事をする暗号学者」と呼ばれる問題で、ITの勉強をしているときにたまたまwikiepdiaで見つけたものです。
もちろん、区別できない紙でもあれば、主催者は◯を、主催者でなければ×を書くことにして、混ぜて開票すればよいのでしょうが、
この問題ではそういった「匿名性を守る道具」を、使わない方法を考えます。
wikipediaの解説には、全員が全員と「秘密のやりとり」をして解決する方法が書かれていました。
解説を読んだ私は、ふーむ、なるほど、とも思いましたが、同時に思いました。
「ちょっと面倒くさすぎない？？」と。
円卓に座っているのに、わざわざ向かいの人とも秘密のやりとりをするなんて、現実的ではありません。
10人となってはなおさらですね。
もっと簡便にならないでしょうか？？
・・・考えてみたら、全然簡単な方法がありました。
考えたのは、次の２種類です。
（１）皆、隣の席の人とだけ内緒話ができる場合の方法
（２）任意の人と内緒話をするのは２人だけで、あとの８人は全員に向けた発言しかしない方法
これらをご紹介したいと思います。
クイズとして解いてみたい方は、下を読む前に、考えてみてください。
それでは、ご紹介します。
（１）皆、隣の席の人とだけ内緒話ができる場合の方法
内緒話というより、耳打ちだけで可能です。
代表者を決め、代表者が１人で隠れてコイントスをして、表だったか裏だったかを左隣りの人に耳打ちで伝えます。
耳打ちされた人は、自分が主催者でなければ受け取った情報をそのまま隣の人に、自分が主催者であれば情報をすり替えて（「表」だったら「裏」に。「裏」だったら「表」に。）隣の人に、耳打ちします。
これを続け、１周して最初の代表者に情報が戻ってきたら、代表者は主催者の有無を判定します。つまり、
伝えたはずの情報が変わっていたら「主催者はいる」、伝えたはずの情報がそのままだったら「主催者はいない」、ということがわかりますから、代表者はわかった結果を発表します。
（ここでもちろん、代表者自身が主催者だったら、情報が変わっていなくても「主催者はいる」、と発言します。）
これでOKです。
情報が変わるのは主催者がいた場合に限るので、当然といえば当然ですね。
そして、誰が情報をすり替えたのかは、誰にもわかりません。
符号の誤り検出に似ているところがありますね。
ちょっと面白いのが、
この方法の発展として、同じようにして、ある質問にYESの人が何人いるかを調べる方法があります。
つまり、内緒話だけで投票を行う方法もあるということです。
要領は次の通り。
代表者は、コインの表裏ではなく、０から９の数字をランダムに決めて、隣の人に耳打ちします。
耳打ちを受けた人は、自分がYESなら伝えられた数字に1を足し、YESでなければ伝えられた数字をそのまま、次の人に耳打ちします。
ただし、1を足して10になる場合は、「０」と伝えます。
こうして一周すると、YESである人の数だけ数字が加算されるので、代表者が最後に、初めに耳打ちした数字と、受け取った数字との差を発表します。（ここでもちろん、自分がYESである場合はさらに1を足します。）
たとえば、初めに耳打ちした数が８で、受け取った数が２ならば、YESである人の数は４人です。（８→９→０→１→２と、４人分増えた）
紙と鉛筆がないときに、ぜひお試しください。
ただし、全員が誠実であることは前提です。（勝手に数字を変えられちゃったら、たまったものではありませんね。）
（２）任意の人と内緒話をするのは２人だけで、あとの８人は全員に向けた発言しかしない方法
これは少し高度ですが、面白いです。
要するに、２人さえ、秘密の意思伝達が可能であれば、主催者の存否を匿名で明らかにすることができる、ということです。
方法は次の通り。
秘密の意思伝達ができる２人はそれぞれ、残りの８人に対して「１」か「０」の情報を秘密裏に送ります。
このとき、
・それぞれの人について、「１」を送るか「０」を送るかは、ランダムに決めます。
・ただし、自分が主催者でない場合は、「１」を送った人数が偶数になるようにし、自分が主催者である場合は、「１」を送った人数が奇数になるようにします。
※たとえば、７人目まではコイントスなどでランダムに決め、８人目は「奇数」か「偶数」かが正しくなるように数字を決めればよいです。
８人はそれぞれ２人から「１」か「０」の情報を受け取ることになります。
この受け取った情報と、自分が主催者であるか否かに基づき、次のように数字を全員に向けて発言します。
・２人から受け取った情報を足し合わせる。
・自分が主催者であれば、さらに「１」を足す。自分が主催者でなければ、そのまま。
・合計値が奇数ならば「１」、偶数ならば「０」と発言する。
これにより８人からそれぞれ「１」か「０」の情報が発信されます。
これらの合計を足して、合計値が奇数であれば、主催者はいるということになり、合計値が偶数であれば、主催者はいないということになるはずです。
目的を達成できる理由は以下の通り。
・誰も主催者でなければ、この方法の結果は偶数になるはずです。秘密の意思伝達ができる2人が「１」を送る数は偶数であり、
８人はそれぞれそれを足し合わせるだけだからです。
ここで、２人のどちらかが主催者であれば、「１」が送られる数は奇数になるし、
８人のうち誰かが主催者であれば、合計値は、１ずれるので奇数になります。
・そして、この方法では誰が主催者であるかの見当をつけることは誰にもできません。
秘密の意思伝達ができる２人(A,B)のうちAにとっては、「１」を送ったはずの人(C)が「０」と発言していても、Bがその人に「１」を送ったからかもしれないし、その人(C)が主催者だからかもしれないので、区別できません。また、「１」を送ったはずの人(C)が「１」と発言していても、Bがその人に「１」を送ってさらにその人(C)が主催者なのかもしれないし、Bがその人に「０」を送ってその人(C)が主催者でないかもしれないので、区別できません。要するに、Bが「０」と「１」どちらをCに対して送ったかがわからないため、Cが主催者であるかはわからないのです。
8人にとっては、「０」と「１」が送られてくるだけで、それ自身からは何の情報も得られないので、誰が主催者であるかは見当のつけようがありません。8人が発言する「１」と「０」の合計値も、元々はランダムに決められた数に基づくものなので、いくつになる傾向があるということもなく、合計値からは何も推測はできません。
〜シミュレーション〜
たとえばAの立場で考えてみます。Aが主催者でないとき、たまたま8人に送る信号がすべて「０」であったとします。
そして、8人(C,D,E,F,G,H,I,J)の発言が、(1,1,1,1,1,1,1,0)であったとします。
誰が主催者である確率が高いでしょうか？
このようになった経緯とその確率を考えると、
・Bが主催者であり、(1,1,1,1,1,1,1,0)を送った可能性
Bが主催者である確率→1/7、 信号がこのようになる確率→1/2^8
・Bが主催者でなく、Cが主催者であり、信号が(0,1,1,1,1,1,1,0,0)であった可能性
Cが主催者である確率→1/7、 信号がこのようになる確率→1/2^8
・Bが主催者でなく、Jが主催者であり、信号が(1,1,1,1,1,1,1,1,1)であった可能性
Jが主催者である確率→1/7、 信号がこのようになる確率→1/2^8
この通り、どの事象も、同じ確率で起こりえたことですから、事後確率を考えても、B〜Jの誰が主催者である確率が高いかはわかりませんね。
以上の方法は、10人でなくとも可能です。n人が容疑者であり、2人さえ秘密の意思伝達ができる状況であれば、
主催者（犯人）がいるか、いないか、を、匿名性を維持しながら調べることができます。
もちろんこれも、皆が作業を誠実に行い、インチキも結託もないことが前提です。
誰もこれ以上の情報を公表しないことを約束する必要があります。
(たとえばCが「Aからは0を受け取ったよ」などと言ってしまうと、それが真実であるかどうかはAやBには分かっているのでCの無実が証明されてしまいます。）
以上、２つの簡便な方法を紹介してみました。
どちらも裏切り者が少しでもいると匿名性を守るという目的を達成できなくなってしまう点では、wikipediaで説明される面倒くさい方法には劣るようです。この辺は「安全性」という項目に関わるお話みたいですね。
情報理論はまだまだ勉強途上ですが、ときどきこういったパズルじみたお話が出てくると、わくわくするものです。
スポンサーサイト
