暗号の安全性と攻撃モデル

暗号方式の安全性を「攻撃者の能力 × 達成目標」で定式化し、ゲームで証明する枠組み。

攻撃モデル（攻撃者の能力）

• CPA (選択平文攻撃): 任意の平文を暗号化させられる。
• CCA1 (選択暗号文攻撃): チャレンジ前に復号オラクルを使える。
• CCA2 (適応的 CCA): チャレンジ後も復号オラクルを使える（最強）。

解読目標（達成すべき秘匿性）

• OW (一方向性): 暗号文から平文を求められない。
• SS / Semantic Secure（強秘匿性）: 平文のいかなる部分情報も漏れない。
• IND (識別不可能性): 2 つの平文のどちらを暗号化したか当てられない。
• NM (頑強性): 暗号文から関連する別の暗号文を作れない。

組み合わせて IND-CPA、IND-CCA などの安全性クラスを定義する。IND-CPA ⇐ IND-CCA のように下位互換の含意関係があり、IND-CPA から IND-CCA への変換は藤崎・岡本変換などで構成できる。

ゲームによる定義

IND-CCA ゲームでは敵 A とチャレンジャ C が対戦する: C が鍵と $b^{\ast }\in \{0,1\}$ を選び、A は暗号化・復号オラクルを $q_e,q_d$ 回叩いた上で $b$ を出力、$b=b^{\ast }$ なら勝ち。アドバンテージ

${\mathrm{Adv}}_{A,\Pi }^{\mathrm{ind}\text{-}\mathrm{cca}}=\mathrm{Pr}[b^{\prime }=b]-\frac{1}{2}\le ϵ(\kappa )$

が無視可能なら安全。証明では困難仮定（LWE、離散対数など）への帰着を game-hopping で行う。より強い合成可能性は Universal Composability で扱う。

FHE における注意

FHE は延性（malleability）を本質とするため CCA2 安全にはなり得ず、IND-CPA が標準。CCA1 安全な FHE の構成は別途研究される。MPC の semi-honest / malicious モデルもこの枠組みの一部。

関連クラスタ: _moc-crypto