前回でapproximation algorithmや、online algorithmはひとまず終了。

今回からは、communicationという場面を想定したalgorithmを学習する。

というより,algorithmという言葉はひとまず、一度退場する。

ここではprotocolという用語をつかう。

具体的な事例 Introduction

婚活中の男性が5名。 女性が5名。
太郎、次郎、三郎、四郎、五郎

はな 美香 たえ みき あき

女性5名、それぞれが、たとえば、はなには四郎が本命であったり、あきには五郎が本命で
あったりという「意中の相手」がいると仮定。ここで大事なのは「本命がだれか」ということは
その女性の心のうちにあるだけで、外部からはわからないということ。

protocolによって達成した目標。
それぞれの男性、女性にとって「重要な情報」が外部にもれることなく、
女性の男性への「好み」「preference」が、かぶっていないかどうかを確認したい。

具体的なprotocolたとえば、無記名投票を女性がするとした場合。
男性、それぞれに何票が投じられたかがわかる。
1票ずつ、男性が得票していたら、女性のpreferenceはかぶっていないということになる。

しかし、この投票を実行すると、
次郎には2票
三郎には1票
五郎には0票のように
男性それぞれの「モテ度のランキング」が明らかにされてしまう。
こういう事態は当事者にとってまずいという問題意識がある。

それでは、こういう「不都合な真実」が公にされないように、
男性と女性の間で「好み」が「1対1対応」になっているかどうかを確認するにはどういう
方法があるか?

あるそうです。

女性5名に、チェックマークを記述することができる紙片を5枚一人一人に配っていく。
男性には、紙片を5枚収納できるグラスコップをもってもらう。

女性は、5枚のうち、1枚にだけチェックマークをいれる。
そしてその5枚をくしゃくしゃにして、外部からどの紙片にチェックマークが入っているか
わからないようにする。
25枚の紙片をシャッフルする。(5枚の紙にはチェックがついている。)
女性は、そのチェックマークのついた紙片だけ、preferenceの男性のグラスコップにいれる。

あとの4人の男性には、なにもチェックをいれていない紙片をいれる。
この作業を5回くりかえす。
グラスコップには5まいの紙片がはいっている。

一郎から順番に、紙片をとりあげ、ひもといていく。
チェックマークがついた紙片が出てきた時点でそのグラスコップに入っている紙片を
ほどくのはやめる。
そして、次のグラスコップの紙片をほどいていく。

もしも、1対1の対応になっていたら、グラスコップすべてにチェックの紙片が1枚ずつはいっている状態に
なっているはず。
もし、1対1になっていなかったら、5このグラスコップのうちのどこかで、ほどいた紙片に一枚もチェックが
ないという事態がおこる。そういう事態がおこった時点で、紙片をほどく作業終了。

こうすると、「不都合な真実」が公にされない状態で、(というか、無記名投票よりはまし)
「1対1の対応」の成立の有無だけを知ることができる。

次の具体例。
ルートを求める計算方法はしらない。
だけど、かけ算をすることはしっている小学生のCharlie

どんな計算でもできる高校生のBob

チャーリー「169のルートは?」
Bob 「13」
チャーリー「13と13をかけ算してみて、ほんとだ169になった」
と確認することはできる。

ZERO PROOF KNOWLEDGE

というそうです。
Wikipedia

暗号学において、ゼロ知識証明(ぜろちしきしょうめい、zero-knowledge proof)とは、ある人が他の人に、自分の持っている(通常、数学的な)命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。ゼロ知識対話証明(ZKIP)とも呼ばれる。

ジャン=ジャック・キスケータらの論文「我が子にゼロ知識証明をどう教えるか(How to Explain Zero-Knowledge Protocols to Your 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さんの跡をつけて合い言葉を盗み聞きするのを防ぐことができる。これは、露出する情報を最小限にするために重要な点である。