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

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

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

• 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

証明可能安全性と帰着

現代暗号の安全性を「絶対」ではなく相対評価する枠組み。『耐量子計算機暗号』『Foundation of Cryptography』で扱われる。「この問題が困難ならばこの暗号を破るのも困難」という形で、計算量的困難性へ帰着して証明する。

計算量的安全性の基礎

• 攻撃を多項式時間で実行できないことを目指す(BPP、確率的チューリングマシン)。
• Negligible Function、PPT(多項式時間)アルゴリズム、一方向関数・トラップドア一方向関数。
• onetime pad は Perfect Secure を達成するが鍵長=平文長で非現実的。

安全性定義

• 公開鍵暗号 $\Pi =(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$ の正当性 ${\mathrm{Dec}}_{sk}({\mathrm{Enc}}_{pk}(m))=m$。
• Semantic Secure は扱いにくいので同値な IND-CCA で定式化。攻撃者と挑戦者のゲームで証明する。
• 統計距離 $\Delta (X,Y)$ で確率分布の近似を評価(計算機の乱数で連続分布を近似する基盤)。

帰着のテクニック

• 攻撃アルゴリズム ${\mathcal{A}}^{\mathrm{Elg}}$ を内部で実行する形で仮定の問題(例 DDH)を解くアルゴリズムを構成し、advantage の不等式 $\mathrm{Adv}({\mathcal{A}}^{\mathrm{Elg}})\le P(\kappa )\cdot \mathrm{Adv}({\mathcal{A}}^{\mathrm{DDH}})+ϵ$ を示す。
• game-hopping: ゲームに IND な変更を繰り返し、自明に困難なゲームへ到達させて元の困難性を示す。
• 帰着の向きに注意(問題の帰着と困難性の帰着は逆)。ElGamal の IND-CPA は DDH 仮定、ひいては離散対数問題の困難性に基づく。
• タイトな帰着ほど良く、128ビット安全性が標準基準。標準仮定(素因数分解・離散対数)への帰着が望ましい。

格子暗号(LWE) / isogeny-based-cryptography / cryptographic-security-models と接続。関連: _moc-life-misc