証明可能安全性と暗号の安全性定義（IND-CPA / IND-CCA）

「安全」を直感で語らない

「この暗号は安全だ」とは何を意味するのでしょうか。鍵を総当たりできない、という説明は不十分です。総当たり以外の近道がないことこそ証明すべき対象だからです。証明可能安全性（provable security）は、この曖昧さを排し、安全を数学の言葉で定義し、定義を満たすことを証明する枠組みです。暗号の基礎的な区分は 暗号の基礎 を前提とします。

証明の核心は3点です。第一に、攻撃者に何ができれば「破れた」と見なすかを攻撃者ゲームで厳密に決める。第二に、攻撃者の計算資源を多項式時間に制限し、勝率の偏りを無視できる量（negligible）かどうかで判定する。第三に、暗号を破る能力から計算困難と信じられている問題（素因数分解、離散対数など）を解く手順を作り、「破れる＝難問が解ける」という帰着で安全を裏づける。

IND-CPA：選択平文攻撃のもとでの識別不可能性

最も基本的な目標が **IND-CPA（Indistinguishability under Chosen-Plaintext Attack）**です。暗号文を見ても、それがどの平文の暗号化なのか分からないことを要求します。これを「攻撃者 vs チャレンジャー」のゲームで定義します。

IND-CPA ゲーム
  1. チャレンジャーが鍵 k を秘密に生成する
  2. 攻撃者は任意の平文を投げ、暗号化結果を好きなだけ得られる（CPA 能力）
  3. 攻撃者が同じ長さの平文ペア m0, m1 を提出する
  4. チャレンジャーが b を {0,1} から無作為に選び、c = Enc(k, m_b) を返す
  5. 攻撃者は c を見て b' を推測する。b' = b なら攻撃者の勝ち

攻撃者の**優位性（advantage）**を |Pr[b'=b] - 1/2| と定義します。手順2で暗号化を自由に試せるのに、それでも優位性が無視できる量に留まるとき、その方式を IND-CPA 安全と呼びます。

ここから重要な帰結が出ます。決定的暗号は IND-CPA を満たせません。同じ平文が常に同じ暗号文になるなら、攻撃者は手順2で m0 を暗号化させ、手順4の c と一致するか見るだけで b が分かるからです。ゆえに IND-CPA 安全には確率的暗号化（毎回異なる乱数・nonce・IV を使う）が必須となります。これは パディングオラクル攻撃 で見た IV の役割の理論的根拠でもあります。

IND-CCA2：復号オラクルまで与えてなお守る

CPA では攻撃者は暗号化しか試せません。しかし現実のサーバーは復号もして応答を返す。エラー応答や挙動の差が漏れれば、攻撃者は事実上の復号オラクルを握ります。これを取り込んだのが **IND-CCA2（適応的選択暗号文攻撃）**です。

CCA2 ゲームでは、攻撃者は手順4で c を受け取った後も、c 以外の任意の暗号文を復号させられます。c をわずかに改変した暗号文 c' を作って復号を頼み、その平文から b を逆算する――こうした攻撃を防げて初めて CCA2 安全です。

帰着：破れるなら難問が解ける

定義を満たすことをどう証明するのでしょうか。直接「破れない」を示すのは不可能です。代わりに**帰着（reduction）**を使います。論理はこうです。

背理法 + 帰着の骨格
  仮定: 暗号 E を非自明な優位性で破る攻撃者 A が存在する
  構成: A を部品として呼び出し、難問 P（例: 素因数分解）を
        効率よく解くアルゴリズム B を組み立てる
  帰結: P は難しいと信じられている → B は存在し得ない
        → よって A も存在し得ない（対偶）

つまり「E を破る」能力を「P を解く」能力へ変換できれば、P が難しい限り E も破れない、と結論できます。証明の品質は変換の**緊密さ（tightness）**で測ります。攻撃者の優位性 ε と難問を解く確率の比、実行時間の増分が小さいほど緊密で、同じ安全性をより短い鍵で得られます。RSA の数理 を素材にした素因数分解問題への帰着が典型例です。

ランダムオラクルモデルの意味と限界

実用的な方式（RSA-OAEP、署名の多く）は、ハッシュ関数を理想化された乱数関数と仮定して証明されます。これが**ランダムオラクルモデル（ROM）**です。

ROM では、ハッシュ H を「同じ入力には同じ乱数、新しい入力には真の乱数を返す巨大な対応表」と見なします。証明の中でこの表は帰着アルゴリズム B が握っており、攻撃者 A が H に問い合わせた入力をすべて観測・操作できます。この自由度のおかげで、現実の SHA-256 では困難な証明が通ります。

理想化を排した標準モデルでの証明が望ましいものの、効率と引き換えになりがちです。実務では「ROM で証明され、長年実戦に耐えた標準方式」を採るのが現実解で、新方式は標準モデルの証明を目指します。

なぜ自作暗号は危険なのか

ここまでの枠組みが、自作暗号を避けるべき理由を理論面から説明します。

設計者が思いつく攻撃を防げても、それは自分が想定した攻撃に限られます。証明可能安全性は「想定外を含む、定義が許すあらゆる攻撃者」に対する保証を与えます。さらに数学的に安全な方式でも、実装が サイドチャネル攻撃 に晒されれば破れます。nonce の再利用は AEAD（認証付き暗号） で見たとおり安全性を一瞬で崩壊させます。

証明可能安全性は「絶対に破れない」という保証ではなく、「前提とした難問が難しい限り、定義したあらゆる攻撃に耐える」という条件付きの強い保証です。だからこそ、定義と証明と査読を経た標準方式を標準パラメータで使うことが、唯一合理的な選択になります。基礎の整理は 暗号の基礎、改ざん検知を含む現代の標準は AEAD（認証付き暗号） を合わせて確認してください。