日々知的刺激を求める社会人駈け出しが好きなことを綴るブログです。〜匿名性を守る投票の方法〜2016-11-24雑記帳##10人の暗号学者に、「宝くじが当たったからご馳走をしたい」という招待状が、差出人不明で届いた。10人は招待状に従って集まり、円卓で豪華な食事を堪能したのだが、招待状の差出人が誰なのかわからず、もやもやしていた。招待状を送った主催者は正体を隠したいのであろうことは理解できるが、この10人の中に主催者がいるのか、いないのか、それだけでも知りたいというのが全員の総意だった。主催者本人も、正体をばらすことはせずとも、「10人の中にいること」自体は表明しても良いと思っているはずだ。主催者がいるのか、いないのかを、主催者が誰かということが全く特定できない方法で明らかにする方法はあるだろうか?##※「誰が主催者である可能性が高いか」ということすら見当がつかないような方法、つまり、「主催者がいるのか、いないのか」ただそれだけが情報としてわかる方法が求められています。これは、「食事をする暗号学者」と呼ばれる問題で、ITの勉強をしているときにたまたまwikiepdiaで見つけたものです。区別できない紙でもあれば、主催者は◯を、主催者でなければ×を書くことにして、混ぜて開票すればよいのでしょうが、この問題ではそういった「匿名性を守る道具」を、使わない方法を考えます。wikipediaの解説には、全員が全員と「秘密のやりとり」をして解決する方法が書かれていました。解説を読んだ私は、ふーむ、なるほど、とも思いましたが、同時に思いました。「ちょっと面倒くさすぎない??」と。円卓に座っているのに、わざわざ向かいの人とも秘密のやりとりをするなんて、現実的ではありません。10人となってはなおさらですね。簡便にならないでしょうか??・・・考えてみたら、全然簡単な方法がありました。考えたのは、次の2種類です。(1)皆、隣の席の人とだけ内緒話ができる場合の方法(2)任意の人と内緒話をするのは2人だけで、あとの8人は全員に向けた発言しかしない方法これらをご紹介したいと思います。クイズとして解いてみたい方は、下を読む前に、考えてみてください。それでは、ご紹介します。内緒話というより、耳打ちだけで可能です。代表者を決め、代表者が1人で隠れてコイントスをして、表だったか裏だったかを左隣りの人に耳打ちで伝えます。耳打ちされた人は、自分が主催者でなければ受け取った情報をそのまま隣の人に、自分が主催者であれば情報をすり替えて(「表」だったら「裏」に。「裏」だったら「表」に。)隣の人に、耳打ちします。これを続け、1周して最初の代表者に情報が戻ってきたら、代表者は主催者の有無を判定します。伝えたはずの情報が変わっていたら「主催者はいる」、伝えたはずの情報がそのままだったら「主催者はいない」、ということがわかりますから、代表者はわかった結果を発表します。(ここでもちろん、代表者自身が主催者だったら、情報が変わっていなくても「主催者はいる」、と発言します。情報が変わるのは主催者がいた場合に限るので、当然といえば当然ですね。誰が情報をすり替えたのかは、誰にもわかりません。符号の誤り検出に似ているところがありますね。面白いのが、この方法の発展として、同じようにして、ある質問にYESの人が何人いるかを調べる方法があります。内緒話だけで投票を行う方法もあるということです。代表者は、コインの表裏ではなく、0から9の数字をランダムに決めて、隣の人に耳打ちします。耳打ちを受けた人は、自分がYESなら伝えられた数字に1を足し、YESでなければ伝えられた数字をそのまま、次の人に耳打ちします。1を足して10になる場合は、「0」と伝えます。して一周すると、YESである人の数だけ数字が加算されるので、代表者が最後に、初めに耳打ちした数字と、受け取った数字との差を発表します。(ここでもちろん、自分がYESである場合はさらに1を足します。)たとえば、初めに耳打ちした数が8で、受け取った数が2ならば、YESである人の数は4人です。(8→9→0→1→2と、4人分増えた)紙と鉛筆がないときに、ぜひお試しください。全員が誠実であることは前提です。(勝手に数字を変えられちゃったら、たまったものではありませんね。)(2)任意の人と内緒話をするのは2人だけで、あとの8人は全員に向けた発言しかしない方法これは少し高度ですが、面白いです。要するに、2人さえ、秘密の意思伝達が可能であれば、主催者の存否を匿名で明らかにすることができる、ということです。秘密の意思伝達ができる2人はそれぞれ、残りの8人に対して「1」か「0」の情報を秘密裏に送ります。・それぞれの人について、「1」を送るか「0」を送るかは、ランダムに決めます。・ただし、自分が主催者でない場合は、「1」を送った人数が偶数になるようにし、自分が主催者である場合は、「1」を送った人数が奇数になるようにします。※たとえば、7人目まではコイントスなどでランダムに決め、8人目は「奇数」か「偶数」かが正しくなるように数字を決めればよいです。8人はそれぞれ2人から「1」か「0」の情報を受け取ることになります。この受け取った情報と、自分が主催者であるか否かに基づき、次のように数字を全員に向けて発言します。・2人から受け取った情報を足し合わせる。・自分が主催者であれば、さらに「1」を足す。自分が主催者でなければ、そのまま。・合計値が奇数ならば「1」、偶数ならば「0」と発言する。これにより8人からそれぞれ「1」か「0」の情報が発信されます。これらの合計を足して、合計値が奇数であれば、主催者はいるということになり、合計値が偶数であれば、主催者はいないということになるはずです。目的を達成できる理由は以下の通り。・誰も主催者でなければ、この方法の結果は偶数になるはずです。秘密の意思伝達ができる2人が「1」を送る数は偶数であり、8人はそれぞれそれを足し合わせるだけだからです。ここで、2人のどちらかが主催者であれば、「1」が送られる数は奇数になるし、8人のうち誰かが主催者であれば、合計値は、1ずれるので奇数になります。・そして、この方法では誰が主催者であるかの見当をつけることは誰にもできません。秘密の意思伝達ができる2人(A,B)のうちAにとっては、「1」を送ったはずの人(C)が「0」と発言していても、Bがその人に「1」を送ったからかもしれないし、その人(C)が主催者だからかもしれないので、区別できません。「1」を送ったはずの人(C)が「1」と発言していても、Bがその人に「1」を送ってさらにその人(C)が主催者なのかもしれないし、Bがその人に「0」を送ってその人(C)が主催者でないかもしれないので、区別できません。要するに、Bが「0」と「1」どちらをCに対して送ったかがわからないため、Cが主催者であるかはわからないのです。8人にとっては、「0」と「1」が送られてくるだけで、それ自身からは何の情報も得られないので、誰が主催者であるかは見当のつけようがありません。8人が発言する「1」と「0」の合計値も、元々はランダムに決められた数に基づくものなので、いくつになる傾向があるということもなく、合計値からは何も推測はできません。〜シミュレーション〜たとえばAの立場で考えてみます。Aが主催者でないとき、たまたま8人に送る信号がすべて「0」であったとします。8人(C,D,E,F,G,H,I,J)の発言が、(1,1,1,1,1,1,1,0)であったとします。信号がこのようになる確率→1/2^8この通り、どの事象も、同じ確率で起こりえたことですから、事後確率を考えても、B〜Jの誰が主催者である確率が高いかはわかりませんね。以上の方法は、10人でなくとも可能です。主催者(犯人)がいるか、いないか、を、匿名性を維持しながら調べることができます。これも、皆が作業を誠実に行い、インチキも結託もないことが前提です。誰もこれ以上の情報を公表しないことを約束する必要があります。(たとえばCが「Aからは0を受け取ったよ」などと言ってしまうと、それが真実であるかどうかはAやBには分かっているのでCの無実が証明されてしまいます。)以上、2つの簡便な方法を紹介してみました。どちらも裏切り者が少しでもいると匿名性を守るという目的を達成できなくなってしまう点では、wikipediaで説明される面倒くさい方法には劣るようです。この辺は「安全性」という項目に関わるお話みたいですね。情報理論はまだまだ勉強途上ですが、ときどきこういったパズルじみたお話が出てくると、わくわくするものです。以前「ワーキングメモリ・トレーニング」の題材として考案•紹介した「不規則な挙動を示す車のモデル」(→■)ですが、すでに研究例があることがわかりました。́ー`))こんな動画まで用意したんですけどね。実はこの先、1万回まで進んでも規則的な動きがでないことがわかり、さらに進めるとなんとこんな形↓が表れ、(車の軌跡を色で示すシミュレーション結果画面)ここから規則的な動きをしながら、イルカの鼻みたいな部分が延々と左下に伸びていくことがわかったんです。...わかったんですが、もうすでになされていました。́ー`)ラングトンのアリ同じようなことが書いてありますね。なんだかちょっとすごい研究のように見えますが、何かに使えるんでしょうか。個人的には、「ライフゲーム」で規則的な動きをする白黒のパターンを見つけるのが流行ったのと同じように、このモデルについてもパターンを見つけることができるので、そういうのは面白いんじゃないかと思ったり。挙動を示す計算モデルともいうことができるかもしれません。ある碁盤の目状の道路と一台の車を想定します。今からこの車は次のルールに従って走行します。◎初めて入る交差点では右折する◎一度来たことがある交差点では...・前回その交差点で右折していた場合は左折する・前回その交差点で左折していた場合は右折するこれだけです。上の図では最初の交差点を右折するところまで示されています。その後この車はどのように交差点を進んでいくでしょうか。最初は右、右、右、右、ですが、次は...左、そして右、右、右、、、あれ、、、、??ってな感じで。何回やり直してもかまいません。これ、やってみるとわかるんですが、車の挙動はなかなか安定なループに落ち着きません。それどころか、あちらこちらにどんどん道を広げて実は100回以上曲がっても行く先が予測不可能なんです。プログラミングでもして一発シミュレーションしてやりたいところですが、環境と時間とスキルが足りなく...(^^;)「ライフゲーム」みたいに面白く使えないかなと思ったり。今のところ僕は二次元のマス目をタップで白黒できるアプリを使って検証していますが、うっかりミスったりしてやるたびに違う挙動に(汗)w規則が現れるのか、いつまでたっても不規則なのか、興味深いところですね。このゲームはオリジナルのつもりなんですが先例があるのをご存じの方がいらしたら教えてください。0Pagetop寓話のうがった見方2011-09-21雑記帳ひねくれたときに考えた、童話のちょっとうがった見方の記録。北風は自分が精一杯やれることをやったのに負けた。太陽はカンカンに照らせば勝てるという計略のもと旅人を照らしつけた。...太陽は称賛に値するか?【ウサギとカメ】ウサギの方が足が速いのは明らかであるのに、カメはどうしてこうも勝ち目のない勝負に挑んだのだろう。ウサギが油断せずにゴールしたら、カメに残るものは敗北感といっそう強まった劣等感だっただろうに。勝つ見込みも得るものもないことにチャレンジするなんて、とてもお勧めされたものではない。それとも、負けない見込みがあったからか。負けない見込み...まぎれもなく、ウサギが昼寝をすることである。「あんまり差を見せつけてしまったらかわいそうだ」というウサギの良心につけこんでカメは勝とうとした。カメの陰湿な謀略が垣間見える。二人目の木こりは金の斧目的でわざと斧を川に放り込んだにも関わらず、褒美を得るチャンスが与えられた。正直に「鉄の斧です」と答えていたら彼も金の斧をもらえたのだろうか。なんだか道理に合わない。考えると、金銀の斧が手に入るチャンスがあること自体に疑念がわいてくる。そもそも最初の木こりも、金銀の斧が与えられる必要があったのか?落とした斧が帰ってくるだけで幸運ではないか。「正直者には落とした斧が返ってくる」...それだけで良かったのだ。金の斧などという余計なものが加わるからこんな不条理が起こっている。・・・断っておきますが、こんなことを本気で考えるほど私はひねくれ者ではありません(^o^;;)こういう視点もあっても良いかもという、提示?子供のころすんなり教訓として受け入れていたものを今一度見直すと面白いですね。(そういえば『青い鳥』の考察なんかも面白いことを書いている人がいたような)ちょっとした脳トレに、かつて読んだ童話を振り返ってみるのはいいことかもしれません。一ヶ月に一つは書いておきたいこのブログ。今月はなかなか忙しく、更新する余裕がありませんでした。(授業もうないのに...)そんなこんなで今日からはテスト週間突入です。前回の天秤問題の答え(期待値のほう)だけ書いておきます。(=約2.42回)解説はまたの機会に。»PagetopプロフィールAuthor:ピエエルお越し頂きありがとうございます。IT・通信系の特許を書く会社員になりました。綴る内容はパズル,脳トレ,吹奏楽,合唱,特許などなど...興味のあるカテゴリからどうぞ、ゆっくりごらんください。パズル・クイズは特に説明のないものは自作です。コメントはマナーさえ守ればどなたでも気楽に書いてOKです。(パスワードは各自の編集用。)※2009年9月22日にCURURUというところから引っ越してきました。