暗号勉強会

あまりコードが出てこない話

ゲーム理論とマルチパーティ計算

はじめに

誰かが不正を働いたり、利潤追求のために動いても安全...それを保証した技術の例にブロックチェーンがある。 この記事では、それを一般化したRational Adversaryという研究分野について書く。まだ理解の浅い部分があるので気持ちだけわかってもらえれば嬉しい。

忙しい人ためのまとめ

  • 利己的に動くパーティとそれに対して非合理的な動きをするパーティがいるMMPCというMPCモデルがある。

  • 各プレイヤーのインセンティヴの指標として満足度やユーティリティというものを使う。

  • 各プレイヤーはt-NCCという性質を持つ関数の下ではマルチパーティ計算から逸脱できない。

出てくる暗号と関係のない用語の簡単な解説

  • maximal set

ある性質Pを満たすAとBがある。この時、A \subseteq BならA=Bである。つまり、集合Aは性質Pを満たすようなmaximal setである。 これがあると、小さい集合について考えなくてよいのである性質を満たすような集合の定義が簡略化される。

どのプレイヤーもその戦略を選ばざるを得ないような状態のこと。「囚人のジレンマ」で有名。

  • 支配

どの戦略を選ぶよりも有効な戦略を支配戦略という。

MMPCモデル

特徴と記号の意味

どのパーティもhonestではないのが特徴。Rationalなパーティはユーティリティを最大化するように行動するパーティで、Adversarial なパーティはそれに対して非合理的な行動で敵対するパーティで最終的には全パーティがプロトコルに従わざるをえなくなる。

  • \mathcal{R} 

MPCをゲームと見なして、プロトコルに逆らう

  • \mathcal{A} 

最大tまでのパーティが連携して、\mathcal{R}に敵対的な行動をする

  • C

Pが使用可能なチャンネルとよばれるチューリングマシンのこと。4つ組で表される。

  • C(P)

Pが使用可能なチャンネルの集合。

MMPCモデルの構成

\mathcal{P}=\mathcal{R}\cup \mathcal{A}と表す。RationalとAdversarialの集合が全体のパーティであることを表す。

チャンネル C= \{ \mathcal{P_I},F_C,state,\mathcal{P_O},\}

プロトコルの通信方法をモデル化したもの。

チャンネルでの一連の処理

  1. \mathcal{P_I}に含まれる各P_iがテープt_i ^ II_iを書き込み、すべての\mathcal{P_i}が書き込むまで待つ。もしタイムアウトしたら\perpをそうでなければI_iをCにインプットする。

  2. このインプットをもとに状態操作関数F_CF_C(I,state)→F_C(O,state')のように適用して、チャンネルの状態を変化させる。

  3. テープt_i ^ O\mathcal{P_O}の各P_iに向けてO_iを書き込む。

プロトコルの処理の定式化

上の一連の処理をランR:=(p,r,\mathcal{A})とする。

  • VIEW_i(r_i,M_i)は各P_iの受け取ったメッセージである。

  • VIEW_i(r_A,M_A)\mathcal{A}の受け取ったメッセージである。\mathcal{A}はまとめて1つの連合とされていることに注意。

  • 各パーティが最後に受け取ったメッセージをOUT_i(R)という。

これが意味するのは、\mathcal{P_I}に含まれる各P_ip_iをそれぞれ実行し、r_iを介して、M_iを受け取っているということだ。そして、Rを繰り返すうちに最後に入手したメッセージはOUT_i(R)と呼ばれる。

MMPCモデルでのインセンティヴ

ユーティリティ

ユーティリティはこのプロトコルインセンティブにあたるものだ。 今回は\mathcal{R}が利益のために動くので、その利潤をプロトコルにおいて数値化する。各パーティP_iは関数f_iについて知りたいという状況を考える。 各ランRに対する関数をプロトコルユーティリティ関数\mathbf{u}とする。


\mathbf{u}={u_1,\dots}

Rationalなパーティはユーティリティ関数u_iと関連付けられる。そしてユーティリティを計算するために、満足度\muというものがある。


\mathbf{\mu}={\mu_1,\dots}

例えば、\mu_iVIEW_i(R)においてどれだけ望むような計算が結果が返ってきたかを表す。

\mathbf{\mu}\mathcal{P}全体の満足度。各満足度\mu_iは以下のように閉区間[0,1]か\perpマッピングされる。\mathcal{A}は邪魔をするだけなので、特にユーティリティを持たない。


\mu_i: \{0,1\}^* \rightarrow [0,1] \cup \perp

\mu _ i(\cdot) =\begin{cases}
[ 0,1 ]\ P _ i \in \mathcal{R}\\
\perp\ P _ i \in \mathcal{A}\\ 
\end{cases}

この個人満足度から全体の満足度を計算するような関数を定義する。ここで、全員の満足度\mu_iから個人のユーティリティu_iを評価するのは、後述のような性質をユーティリティが持つため、個人の満足度だけでは測れないポイントがあるからだ。

さて、各パーティP_iはそのランRで\mathcal{R}が得られた全体の満足度\mu(R)を計算できるu'={u_1,\dots}という関数の集合とする。定義は


u'_i: \{0,1\}^* \rightarrow [0,\infty]

このu' _ iu _ i(R)=u' _ i(\mu(R))という性質を持ち、Rの関数であった\mathbf{u}を満足度を介することで評価できる。 ユーティリティには以下の3つのような性質がある

  1. P_iは学習するとu_i(R)が上昇する。

  2. P_ii\neq jであるようなP_jが学習するとu_i(R)が下降する。

  3. P_ii\neq jであるようなP_jOUT_i(R)=f_i(x)だとu_i(R)=0になる。

t-NCC関数

定義に向けた準備

関数の入力をビットから文字列に一般化することを考えたい。\mathbf{f}:X \rightarrow Yn変数関数とし、\mathcal{P = R\cup A}, |P| = n 、そして\mathbf{u}プロトコルユーティリティ関数とする。各パーティの入力\mathbf{x}\mathbf{x'}は以下のように定義される。


\mathbb{x}=\{\mathbf{x} _ \mathcal{A},\mathbf{x} _ \mathcal{R}\}\\
\mathbb{x'}=\{\mathbf{x'} _ \mathcal{A},\mathbf{x'} _ \mathcal{R}\}

ここで、\mathbf{x'} \leftarrow X とし、\mathbf{x}' _ {\mathcal{R}}=\mathbf{x} _ {\mathcal{R}}かつ、\mathbf{x} _ AをAによる入力\mathbf{x'} _ Aに置き換えるという処理\mathbf{x'} _{\mathcal{A}}\leftarrow A(\mathbf{x} _ {\mathcal{A}})を使っている。すなわち、\mathbb{x'}\mathbb{x}はAによって置き換えられた部分だけ違う。これは\mathcal{A}が自分の入力を変えるようなシナリオを想定している。

新しい概念を導入する。入力から任意の値を得ようとする行為を戦略(strategy)という。

  • Eqv _ f(i, x _ i)\forall \mathbf{x} _ {−i}\forall x \in Eqv_f(i, x _ i)について、f(x _ i,\mathbf{x _ { -i}})=f(x,\mathbf{x _ { -i}})を満たすようなxのmaximal setである。なお、ここ以降で登場する記法の意味は以下である。

(x _ i,\mathbf{x _ { -i}}) =  \mathbf{x} = \{ x _ 1,x _ 2,\dots,x _ {i-1},x _ i,x _ {i+1},\dots,x _ n \} \\
(x' _ i,\mathbf{x _ { -i}}) = \{ x _ 1,x _ 2,\dots,x' _ {i-1},x _ i,x _ {i+1},\dots,x _ n \}
  • \Sigma ' _ i(x_i)を、あるx \in Eqv f(i, x_i)をCに送った後、y_iを出力するP_iの戦略の集合する。

  • \sigma^* _ i(x_i)x_i を C に送った後、 y_iを出力として得る戦略とする。

この定義から分かるように、\Sigma ' _ i(x_i)\sigma^* _ i(x_i)i番目の入力が変わっているが、fの値は変えていない。 戦略に関する記号は4つ登場するが意味は以下である。

  • \mathbf{\Sigma}'\mathcal{R}の戦略のベクトルの集合。

  • \mathbf{\sigma^{*} }\mathcal{R}の戦略のベクトル。各パーティに戦略が定まっている。\mathbf{\sigma^{*}}=\{ \sigma^{*} _ 1(x _ 1),\sigma^{*} _ 2(x _ 2),\sigma^{*} _ 3(x _ 3),\dots \}

  • \Sigma'(x _ i)x_iを別の入力xに変えても変わらないP _ iの戦略の集合

  • \sigma^{*}(x _ i)P _ ix_iを入力する戦略

  • \mathbf{\sigma _ {-i} }=\mathbf{(\sigma _ {\mathcal{R}}) _ {-i}}

t-NCC関数の定義

以上の定義を利用して、\mathbf{f}t-Non-Cooperatively Computable Function (t-NCC 関数) と呼び、すべての P_i \in Rに対して、\mathcal{A}, \mathcal{|A|} \leq tかつ、入力の分布 X の下で 以下を満たすような関数として定義できる。

  1. μ _ i(x _ i, \mathbf{x _ \mathcal{A}})=0,、つまりx_i\mathbf{x_A}のみからf_i(\mathbf{x})については何も知ることができない.(これは\mathcal{A}\mathbf{x}_\mathcal{A}P_iに与えるような例を回避するため)

  2. すべての\mathcal{A},iについて, fi(\mathbf{x'}) = fi(\mathbf{x})、つまり\mathcal{A}は入力を変えることで関数の値を変えられない・.

  3. すべての\mathcal{A}について,P_iは,自分の正しい入力x_iをCに与えることで,他の異なる入力を与えるのと同じくらいのユーティリティを得られる。つまりプロトコルに従わざるを得ない。数式としてはすべての1 \leq i \leq nと すべての\sigma_i\notin\Sigma '_i(x_i)について以下のようにあらわせる。

f:id:ATen:20200601234113p:plain

この数式の意味は直感的には、P_iが自分の入力を正規の入力から変更しても、正規の入力\mathbf{x_R}より低いユーティリティの期待値しか得られないことを意味する。

MMPCのナッシュ均衡

パーティ\mathcal{P}=\mathcal{R}\cup \mathcal{A}\mathcal{R}の戦略\mathbf{\sigma}*が(\epsilon-)ナッシュ均衡であるとは、すべてのパーティと全ての戦略と全ての\mathcal{A}について以下を満たすことである。ここで\mathcal{P}\mathbf{X}から入力を手に入れ、チャネル構造C(P)とプロトコルユーティリティ関数\mathbf{u}を持つ。

f:id:ATen:20200605115544p:plain
(ε-)ナッシュ均衡

この式は、直感的には戦略のユーティリティの期待値に無視可能な程度にしか差がない状態を意味する。ゲーム理論ナッシュ均衡をうまく確率的なものに置き換えている。(?)


E_{\mathbf{X}}[u_i( (\sigma_{-i},\mathbf{\sigma^{*} _{-i} } ),\mathbf{r} , \mathcal{A} ) ]

これの意味を見てみるとまず((\sigma _ {-i},\mathbf{\sigma^{*}  _ {-i} } ),\mathbf{r} , \mathcal{A})はランRのことである。さらにu _ i( (\sigma _ {-i},\mathbf{\sigma^{*} _ {-i} } ),\mathbf{r} , \mathcal{A} )となっていることからこれは、ランRにおけるP _ iのユーティリティである。(\sigma _ {-i},\mathbf{\sigma^{*} _ {-i} } )はひとつの戦略のベクトルのうちP _ iに対応(ベクトルのi番目)する戦略を入れ替えたものである。

入力は分布Xから与えられるから、数式全体としてはP _ iが戦略を変えたときのランRにおけるP_iのユーティリティのXにおける期待値である。

弱支配戦略の繰り返し削除

\mathbf{\sigma}が以下のような二つの条件を満たすとき、

 [ \mathbf{\sigma} < \mathbf{\sigma}^{'} | \mathbf{\Sigma}' ]

であるような\mathbf{\sigma}'の被弱支配戦略という。ここで\mathcal{P}\mathbf{X}から入力を手に入れ、チャネルCプロトコルユーティリティ関数\mathbf{u}を持つ。

(1) この時、i番目の入力が入れ替えられた全ての戦略 \mathbf{\sigma} _ {-i} \in \mathbf{\Sigma}' と全ての\mathcal{A}に対して、i番目を戦略\mathbf{\sigma}'で入れ替えたときは、\mathbf{\sigma}で入れ替えたとき以上のユーティリティの期待値を得られる。

f:id:ATen:20200605120635p:plain
(1)

(2) i番目の入力が入れ替えられたある戦略\mathbf{\sigma}'_{-i} \in \mathbf{\Sigma}'とある\mathcal{A}に対して、 i番目を戦略\mathbf{\sigma}で入れ替えたときは、\mathbf{\sigma}'で入れ替えたときよりも一定の値小さいユーティリティの期待値を得られる。(正しいか分からない、εをどう扱うか)

f:id:ATen:20200605121241p:plain
(2)

さて、この条件を参考に、弱支配戦略の繰り返し削除を以下のように行える。

f:id:ATen:20200605150400p:plain
(3)

この式は直感的にはある戦略よりもユーティリティが小さい戦略が存在する限り、それを再帰的に引いていくという処理である。\mathbf{\Delta^{l}}は被支配戦略の集合のベクトルともいえる。 実際l=1,i=1とすると初期値\Sigma_{i}^{l-1}=\Sigma^{0}となり


\begin{eqnarray}
\Sigma^1 _ 1 &= \Sigma^0 _ 1- \Delta^{1} _ 1\\
\Sigma^2 _ 1 &= \Sigma^1 _ 1 - \Delta^{2} _ 1\\
\Sigma^3 _ 1 &= \Sigma^2 _ 1 - \Delta^{3} _ 1\\
\Sigma^4 _ 1 &= \Sigma^3 _ 1 - \Delta^{4} _ 1\\
&\vdots
\end{eqnarray}

これを行うと、

 [ \mathbf{\sigma} < \mathbf{\sigma}^{'} | \mathbf{\Sigma}' ]

であるような\mathbf{\sigma}は残らない。よって被支配戦略は消え、支配関係にない選択されうる戦略だけが残る。

t-secure preferred protocol

MMPCモデルによるプロトコルはt-secure preferredを満たすのが望ましい。戦略のベクトル\mathbb{\sigma^{*}}が以下の3つの性質を持つなら入力の分布が\mathbf{X}の関数のベクトル\mathbf{f}に対するt-secure preferredプロトコルを構成する。ここで\mathcal{P}\mathbf{X}から入力を手に入れ、チャネル構造C(P)とプロトコルユーティリティ関数\mathbf{u}を持つ。

  • 安全性と正しさ(シュミレータから導かれる結果の解釈はこれでOKなのか?)

w=(\mathbf{OUT _ {\mathcal{R}} (\sigma^{*} _ {\mathcal{R}},r,A)},\mathbf{VIEW _ {\mathcal{A}} (\sigma^{*} _ {\mathcal{R}},r,A)})

のサンプルwと以下のように生成されたサンプルw'の見分けがつかないようなシュミレータSが存在することが安全性の定義である。実際に得た入出力がランダムなものと区別できなければ安全ということ。

サンプルw'の生成方法

Sは最初\mathbf{x}_\mathcal{A}を持っている。そのままyを出力してもいい。その場合は


w'=(\perp_\mathcal{R},y)

を得る。それか、\mathbf{x^{'}}_\mathcal{A}を生成してf _ \mathcal{A}(\mathbf{x^{'}})を受け取ってもよい。その場合は


w'=(f _ \mathcal{R}(\mathbf{x^{'}}),y)

を得る。

\mathcal{\sigma^{*}} (\mathbf{x}) は 任意の\mathcal{P}の分割に対してナッシュ均衡が成立している。

  • 削除されない戦略

任意のパーティ\mathcal{P}の分割と、任意のパーティP_i \in\mathcal{P}に対して、\sigma^*_i (x_i) は繰り返し削除で残る。つまり弱支配されない最小の戦略になっている。

まとめ

ゲーム理論とマルチパーティ計算を組み合わせることで、インセンティブを安全性の指標にするという面白い試みだと思った。経済学と暗号の組み合わせといえばブロックチェーンもあるが、この分野の研究が進んだらマルチパーティ計算にも新しい安全性が生まれるのかと思ったり。

参考文献

Rationality and Adversarial Behavior in Multi-party Computation (Extended Abstract)