book-loverのブログスマートフォン用の表示で見るbook-loverのブログこの広告は、90日以上更新していないブログに表示しています。algorithmはひとまず終了。今回からは、communicationという場面を想定したalgorithmを学習する。いうより,algorithmという言葉はひとまず、一度退場する。ここではprotocolという用語をつかう。Introduction婚活中の男性が5名。あき女性5名、それぞれが、たとえば、はなには四郎が本命であったり、あきには五郎が本命であったりという「意中の相手」がいると仮定。ここで大事なのは「本命がだれか」ということはその女性の心のうちにあるだけで、外部からはわからないということ。protocolによって達成した目標。女性の男性への「好み」「preference」が、かぶっていないかどうかを確認したい。具体的なprotocolたとえば、無記名投票を女性がするとした場合。男性、それぞれに何票が投じられたかがわかる。1票ずつ、男性が得票していたら、女性のpreferenceはかぶっていないということになる。五郎には0票のように男性それぞれの「モテ度のランキング」が明らかにされてしまう。いう事態は当事者にとってまずいという問題意識がある。男性と女性の間で「好み」が「1対1対応」になっているかどうかを確認するにはどういう方法があるか?あるそうです。女性5名に、チェックマークを記述することができる紙片を5枚一人一人に配っていく。男性には、紙片を5枚収納できるグラスコップをもってもらう。女性は、5枚のうち、1枚にだけチェックマークをいれる。その5枚をくしゃくしゃにして、外部からどの紙片にチェックマークが入っているかわからないようにする。25枚の紙片をシャッフルする。(5枚の紙にはチェックがついている。)女性は、そのチェックマークのついた紙片だけ、preferenceの男性のグラスコップにいれる。あとの4人の男性には、なにもチェックをいれていない紙片をいれる。この作業を5回くりかえす。グラスコップには5まいの紙片がはいっている。一郎から順番に、紙片をとりあげ、ひもといていく。チェックマークがついた紙片が出てきた時点でそのグラスコップに入っている紙片をほどくのはやめる。次のグラスコップの紙片をほどいていく。1対1の対応になっていたら、グラスコップすべてにチェックの紙片が1枚ずつはいっている状態になっているはず。1対1になっていなかったら、5このグラスコップのうちのどこかで、ほどいた紙片に一枚もチェックがないという事態がおこる。いう事態がおこった時点で、紙片をほどく作業終了。すると、「不都合な真実」が公にされない状態で、(というか、無記名投票よりはまし)「1対1の対応」の成立の有無だけを知ることができる。ルートを求める計算方法はしらない。「13」チャーリー「13と13をかけ算してみて、ほんとだ169になった」と確認することはできる。KNOWLEDGEというそうです。proof)とは、ある人が他の人に、自分の持っている(通常、数学的な)命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。ゼロ知識対話証明(ZKIP)とも呼ばれる。Children)」で紹介されているのが、この洞窟の問題の例である。ここで、証明者はP(Prover)、検証者はV(Verifier)と略すのが一般的なのでこれを用いて説明する。Pさんが、魔法の扉を開くための合い言葉を手に入れたとする。その魔法の扉は、ある洞窟の一番奥にあり、洞窟は途中で分かれて奥でつながっていて魔法の扉で仕切られているとする。Vさんはお金を払ってでも合い言葉が知りたいが、Pさんが本当の合い言葉を知っていると確認できるまでは払いたくない。Pさんは教えてもいいが、お金をもらうまでは教えたくない。そこで二人は、合い言葉そのものは教えることなく、正しい合い言葉を知っていることだけ証明する方法を使うことになる。Vさんは洞窟の外で待ち、Pさんだけ入る。左右の分かれ道をそれぞれA,Bと呼ぶことにすると、PさんはAかBどちらかの分かれ道をランダムに選んで奥に入ることになる。次にVさんは分かれ道の入り口まで行き、どちらかの道をランダムに選ぶ。Pさんに、ランダムに選んだその道から出てきてほしいと大声で伝える。Pさんが合い言葉を知っているならそれに答えるのは簡単である。反対側なら魔法の扉を開けて通るだけでよい。VさんはPさんがどちらから入ったのかは知らないという点に留意。実はPさんが合い言葉を知らないという場合もあり得る。この場合、入った道から出てくることしかできない。Vさんがランダムに出てくるべき道を選ぶので、Pさんがリクエストに応えられるのは50%の確率である。この二人がこの試みを何度も繰り返せば、Pさんがすべてのリクエストに応えるのはほとんど不可能になる(20回繰り返したら、約0.0001%となる)。これなら、複数回のリクエストに応えられたならVさんはPさんが確かに合い言葉を知っていると納得できる。この例だと、そんな複雑な手続きをせずにVさんがPさんに「片方の道から入って反対の道から戻ってこい」と言うだけで証明ができるようにも思えるかもしれない。この方法だと、確かに証明はできるものの、合い言葉を盗めてしまう可能性が残ってしまうのだ。Pさんが入る道はランダムに決め、それをVさんがわからないようになっていてこそ、VさんがPさんの跡をつけて合い言葉を盗み聞きするのを防ぐことができる。これは、露出する情報を最小限にするために重要な点である。月別アーカイブはてなブログをはじめよう!book-loverさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。