ZKとPOKに関する話

今日は色々と話をしていた. その中で人の疑問と自分の疑問が解消されたのでメモっておく.
POK (Proof of Knowledge) とZK (Zero Knowledge) は微妙に違う. ZKPOKの場合, ZKかつPOKであることを示さないといけない. ということはZKの方で定義から健全性を示す必要がある. しかし, 健全性を示さずにPOKの方でサンプルを取るアルゴリズム (Sample) と知識を引き出すアルゴリズム (Knowledge Extractor) を作って終わりにしている証明が結構ある.
で, なぜこれが正当かという話.

何をやっているのかよく分からないけれど正しい検証者をκ(x)+ε(x)の確率で納得させる証明者P*を考える. Sampleは共通入力xをインプットとして, P*用の乱数テープを固定して, 検証者のviewの列を吐きだす (P*に対してblack-box accessしかしていない点注意). Knowledge Extractorに共通入力xと検証者のviewを食わせるとKnowledge Extractorは(x,w)または⊥を出力する. (x,w)を出力したときには関係Rに入っている確率はP*がどれだけ検証者を納得させるかによる. ここでxは任意の文字列で議論をおこなっている点注意.

Knowledge Extractorが存在するとすれば, xが言語L_Rに含まれない場合には, P*がVを納得させる確率は高々κということが言える. よって, Knowledge Extractorを作れた場合には健全性も示せている.

あー, すっきりした.

別の話なんだけど, 量子計算でユニタリー行列による演算を物理的にどうするのかってが知りたい. 古典の方でCPUの内部でどうやって0,1を切り替えているのかもおぼろげにしか覚えてないや. チューリングマシンだから良いか.