本記事は 暗号学一人アドベントカレンダー 第3日目の記事です。本来の予定のHistorical Cryptoの話から予定を変更してお届けします。
過去にEncrypt-then-MAC vs MAC-then-Encryptを説明した記事でも若干触れている暗号の安全性の定義の話をします。
TL;DR
実質的には「鍵を知らない攻撃者は暗号文から何も情報が読み取れてはいけないよ」ということをいろんな方法で言っているだけです。
One-Time PadとPerfect Secrecy
（ここでいうPerfect Secrecyは字面は似ていますがTLS等の文脈で出てくるPerfect Forward Secrecyのことではありません）
情報理論の上で完全なセキュリティを持った暗号というものが理論上は存在していて、それは「平文と同じ長さのランダムな文字列を通信の度に毎回生成し、それを鍵としてXORにより暗号文を得る」という、One-Time Pad(Vernam暗号ともいう)というものです。とはいえ、これは理論上でしか存在しないとされています。もし平文と同じ長さのランダムな文字列をある二者が他の人に盗聴されずに共有できるのであればもはや暗号は必要ではなく平文そのものを安全に共有できるからです。
暗号の定義
以下、暗号(cipher)を鍵空間K, メッセージ空間M, 暗号文空間C上に定義される「効率のよい」アルゴリズム \( E: K \times M \to C, D: K \times C \to M \) の組(E, D)と定義します。
また、E, Dは\( \forall m \in M, k \in K, D(k, E(k, m)) = m \) を満たすものとします（暗号化して復号化したら元に戻る、ということ）。
Perfect Secrecy
\( len(m_0) = len(m_1) \) である \( \forall m_0, m_1 \in M \) と \( \forall c \in C \) について \(Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]\) を満たすときに暗号(E, D)はPerfect Secrecyを持つといいます。つまり、長さの一致する2つの文字列について、ある鍵で暗号化した結果同じ暗号文になる確率が等しいときにPerfect Secrecyを持つといいます。これは、どんな強力な解読者でも暗号文だけを見て対応する平文を区別＝予想することができない、ということを意味していて、暗号文のみを得ている場合に成立する攻撃が存在しないことを意味しています。
残念ながらPerfect Secrecyを実現するためには鍵長がメッセージ長と等しいかそれ以上の長さが必要であることが知られています。
Pseudo-Random Generator/Function
One-Time Padが理論上でしか存在できない以上、もうちょっとマシな方法はないのか？ということで、一般的にはストリーム暗号ではPseudo-Random Generatorと呼ばれる、より小さいシード空間から決定論的に乱数列を生成する関数を使います（\(G: \{0, 1\}^s \to \{0, 1\}^n (s << n)\)）。
ブロック暗号においてはPseudo-Random Functionと呼ばれる、「XからYへの関数のうちランダムな関数を1つ選んだもの」と「\(F: K \times X \to Y\)を満たすランダムなF」が事実上区別できないような関数の集合を使って暗号を実現します。暗号鍵kを一つ選ぶことでXからYへの関数が一つ確定し、それがXからYへの関数の集合からランダムに一つ関数を取り出したものと区別がつかなければ、kがわからない限りXからYへのマッピングを行えない、という性質を使います*1。
Semantic Security
Perfect Secrecyほどではないけれど、暗号文から得られる情報量が無視できる量であることを示すセキュリティ定義としてSemantic Securityという概念があります。
- 挑戦者(Challenger; 「呼び掛け器」という訳があるらしい)は0か1かを決める: \( b \gets {0,1} \)
- 攻撃者(Adversary)は等しい長さの平文
m_0,m_1を挑戦者に送る - 挑戦者はそれを暗号化して返す: \(c \gets E(k, m_b)\)
- 攻撃者は送られてきた暗号文
cがm_0のものかm_1のものか予想する - それぞれ
W_0,W_1を「挑戦者がb=0指定のとき予想が成功する事象」「挑戦者がb=1指定のとき予想が成功する事象」とする - ここですべての「効率のよい」攻撃者Aに対して\(Adv_{SS}[A, E] = | Pr[W_0] - Pr[W_1]| \)が無視できるほど小さいとき、暗号(E, D)は(選択平文攻撃(CPA)に対して)Semantically Secureであるという
- 要するに、b=0であってもb=1であっても（ほぼ）同じ確率でしか攻撃者は正解できない→暗号文だけからは何の情報も得られていない！ということ。
ブロック暗号で初期化ベクトルが必要な理由
決定論的なブロック暗号はSemantic Securityを満たすことができません。その理由として、攻撃者が複数回挑戦者に対して暗号化の問い合わせが可能な場合（十分に考えられる状況）、(m_0, m_0), (m_0, m_1)という組を問い合わせるだけで「bが0なのか1なのか」＝「右を暗号化して返すか左を暗号化して返すか」を知ることができてしまうからです。なので、挑戦者（＝暗号化を行う側）は暗号化を行うたびにランダムな初期化ベクトルをセットで付与して返すことで、「同じ内容の暗号化クエリを受けても違う結果を返す」ことができ、Semantic Securityを維持できます。
Indistinguishability
もう一つ使われるセキュリティ定義としてCiphertext Indistinguishabilityというものがあります。この語は日本語では「秘匿性」と訳されていますが英語の直訳では「区別不可能性」という意味が近いです。
（解説としては StackExchangeの質問 "Easy explanation of “IND-” security notions?" が良さそう）
選択暗号文攻撃は「攻撃者が（挑戦の対称になっているもの以外の）任意の暗号文の復号を復号器に問い合わせることができる」という割と極端な状態（とはいっても有り得る）でも指定された暗号文は m_0 か m_1 のものか区別できない、という性質を示しています。
だいぶ長くなってしまいましたが次回・次々回はハッシュ関数の安全性の定義について書きます。
