安永先生の本「暗号理論入門」では第３章で計算量的な安全性を導入します。
ここからは勉強したことのメモとLean4による定義および定理を述べますが、理論の背景は述べません。ぜひ安永先生の本で勉強してください。またLean4による証明も記載しませんが、Githubには公開するので参考にしてみてください。
第３章冒頭では完全識別不可能性をベースに計算量的識別不可能性を定義します。攻撃者Aの使える計算量をtに縛るとともに、確率の一致の代わりに確率の差分が一定の精度εに収まってしまうことで計算量的識別不可能性を定義します。
ただこの定義だと任意のm0, m1 について暗号文の確率分布が一定精度でしか識別できない、という定義になります。普通の攻撃では１つの暗号文を入手してそこから情報漏洩が起きるかどうか、ということです。このような観点で定義されたのが「意味的安全性」という安全性です。解読までできなくても情報漏洩はあり得ること、事前に平文について一定の知識を知っていることはよくあること（平文のフォーマットがXMLとか）、などを加味した定義が以下の通りです。
定義3.4 意味的安全性 共通鍵暗号(Enc, Dec)が(t, α, ε)-意味的安全性であるとは、計算量t以下の任意の攻撃者(A1, A2)に対し、シミュレータSで(A1, S)の計算量がt+α以下のものが存在して、
$$p_a = Pr [(M,h,R,st) \leftarrow A_1 ; m \leftarrow M ; a \leftarrow A_2 ((Enc_K(m), h(m), st) : R(m, a)=1]$$
$$p_s = Pr [(M,h,R,st) \leftarrow A_1 ; m \leftarrow M ; s \leftarrow S(h(m), st) : R(m, s)=1]$$
と定めた時、
$$| p_a - p_s| \le \epsilon $$
を満たすことです。
登場人物が多すぎて面食らいますよね。何を言ってるんでしょうか。$p_a$は攻撃者からの情報漏洩の確率、$p_s$は模倣者による同じ情報が得られる確率、です。その差分が小さいことを安全としていることがわかります。
次に$p_a$を眺めてみます。攻撃者は攻撃前提と成功基準を全て自分で決めています。攻撃前提となる平文分布M, 平文に関する事前情報h(m), 成功基準R(m, a), それと$A_2$への引き継ぎ情報stをすべて$A_1$が決めて出力します。次に平文mを出力し、その暗号文、事前情報h(m), 引き継ぎ情報stを$A_2$に渡しています。$A_2$は漏洩情報をaとして出力します。最後にRがmとaを照らし合わせて情報漏洩があったかを確認します。Rは情報漏洩があれば1、なければ0を出力します。
次に$p_s$を見てみましょう。攻撃者$A_2$の代わりにシミュレータSが登場します。Sは事前情報h(m)と引き継ぎ情報stはもらいますが暗号文はもらいません。そしてらしきものsを出力します。最後にRがmとsを照らし合わせて情報漏洩があったかを確認します。
Sは暗号文を知りませんからその出力sは適当です。それでもRの出力確率が$p_a$の場合とほぼ同じ、というのがこの定義です。たしかに$A_2$は、肝心の暗号文をもらっていないSで模倣されているので、実は$A_2$は大したことをしていない、というのが意味的安全性の意味です。
実はこのh(m), Rなどが登場する複雑な定義は、慣れ親しんだ攻撃者$(A_1, A_2)$に基づく識別不可能性の定義と同値であることがわかります。そちらの定義は簡単すぎて拍子抜けします。
定義3.5 (t, ε)-識別不可能性 共通鍵暗号方式(Enc, Dec)が(t, ε)-識別不可能であるとは、計算量t以下の任意の攻撃者$(A_1, A_2)$に対して、
$$ p_b = Pr [ (m_0, m_1, st) \leftarrow A_1 ; c\leftarrow Enc_K(m_b) : A_2 (c,st)=1]$$
と定めた時、
$$| p_0 - p_1| \le \epsilon $$
を満たすことです。
そういうわけで、おそらく今後定義3.5を計算量的安全性の定義として活用していくのだろうと思います。
両者は厳密にはεの定数倍、定数差程の違いを許した同値関係になります。具体的には以下の２つの定理が成り立ちます。
定理3.1 共通鍵暗号方式(Enc, Dec)は、(t, α, ε/2)-意味的安全であれば、(t, ε)-識別不可能である。ここでα≧0は任意の値である。
定理3.2 共通鍵暗号方式(Enc, Dec)は、($t + t_M + t_h + t_R$, ε)-識別不可能であるとき、($t, t_{Gen} + t_{Enc}$, ε)-意味的安全である。
ただし$t_M$は$M$から平文をサンプルする計算量、$t_h$は$h$を評価するための計算量、$t_R$は$R$を評価するための計算量である。また$t_{Gen},\, t_{Enc}$は鍵生成と暗号化の計算量である。
次回は定義3.4と3.5、定理3.1と3.2をLean4で形式化したものをお見せします。
