適応的選択暗号文攻撃

研究

最近，公開鍵暗号の安全性に詳しい学生さんから適応的選択暗号文攻撃に対して識別不可能性を持つ公開鍵暗号系の構成方法についてレクチャーを受けていました．とても奥が深くて大変勉強になりました．ほっておくと忘れそうなので簡単にまとめておこうと思います．

適応的選択暗号文攻撃に対する識別不可能性は公開鍵暗号の安全性概念の中でも非常に強いものの一つです．英語では indistinguishability against adaptive chosen ciphertext attacks と呼ばれますが，非常に長いのでほとんどの場合，IND-CCA2安全性と省略されます．

さてIND-CCA2安全性の定義は結構面倒なので，まずは公開鍵暗号系の最も基本的な安全性である選択平文攻撃に対する識別不可能性(indistinguishability against chosen plaintext attacks; IND-CPA安全性)について説明して，それを拡張することで説明していこうと思います．

現代暗号の多くの安全性概念は，敵対者と挑戦者のゲームを通じて定義されます．敵対者は暗号プロトコルに応じた挑戦者との通信から秘密の情報を盗み出そうとします．もし敵対者がどうやっても情報を盗めないことが証明できれば，その暗号プロトコルはそのゲームに応じた攻撃方法に対して安全だという結論が得られることになります．

それではまずIND-CPAゲームで公開鍵暗号のIND-CPA安全性の定義を見てみましょう．敵対者，挑戦者ともに公開鍵（暗号化鍵）pkは既に持っているところからスタートです．

  1. 敵対者は二つのメッセージm_0とm_1を任意に選び，その両者を挑戦者に渡す．
  2. 敵対者は二つのメッセージm_0とm_1のどちらかを確率1/2づつで選び，公開鍵pkで暗号化する．その暗号文cを敵対者に渡す．
  3. 敵対者は挑戦者から受け取ったcがどちらのメッセージの暗号文かを当てる．もし当たれば敵対者の勝ち，外れれば敵対者の負け．

図で書くとこんな感じになります．

このIND-CPAゲームは公開鍵暗号系の任意の二つの暗号文が区別すらできない（したがって暗号文の元のメッセージが何かも分かるはずはありません．）ということを特徴付けています．敵対者は当てずっぽうに答えたとしても確率1/2で勝てますが，敵対者がどんなに頑張っても1/2とほとんど変わらない確率でしか勝てないならば，その公開鍵暗号系はIND-CPA安全であると言えます．

次にこのゲームを少し拡張して選択暗号文攻撃に対する識別不可能性(indistinguishability against chosen ciphertext attacks; IND-CCA1安全性)を定義します．IND-CCA2とは違いますので注意して下さい（「適応的」の有無が違いです）．IND-CCA1安全性はIND-CPA安全性より強い安全性ですが，IND-CCA2安全性には若干劣ります．

IND-CCA1ゲームは二つのステージから成ります．第一ステージでは敵対者は暗号文を平文に戻してくれる復号オラクルと通信を行います．敵対者は復号オラクルに暗号文を送ってそれを復号してもらうことで暗号系についての何らかの情報（例えば秘密鍵）を集めようとします．第一ステージを図にすると以下のような感じになります．

第一ステージが終了したら，そこで得られた情報を持って第二ステージに進みます．第二ステージではIND-CPAゲームを行います．通常のIND-CPAゲームと違うのは第一ステージで敵対者が何らかの情報を得ている可能性がある点です．この点でより敵対者に有利な状況であるといえます．もしどんな敵対者もこのゲームにほぼ1/2の確率でしか勝てないのならば，その公開鍵暗号はIND-CCA1安全であると言います．簡単にまとめると以下のようになります．敵対者，挑戦者は公開鍵pk，復号オラクルはpkに対応する秘密鍵skを入力として受け取ってゲームスタートです．

  • 第一ステージ
  1. 敵対者は任意の文字列を暗号文として復号オラクルに渡す．復号オラクルはskを使って復号した文章を敵対者に送り返す．このやりとりを敵対者は任意回繰り返す．
  • 第二ステージ
  1. 敵対者は二つのメッセージm_0とm_1を任意に選び，その両者を挑戦者に渡す．
  2. 敵対者は二つのメッセージm_0とm_1のどちらかを確率1/2づつで選び，公開鍵pkで暗号化する．その暗号文cを敵対者に渡す．
  3. 敵対者は挑戦者から受け取ったcがどちらのメッセージの暗号文かを当てる．もし当たれば敵対者の勝ち，外れれば敵対者の負け．

IND-CCA1安全性は，敵対者が暗号文に対応する平文が入手できるような状況下でも安全であるということを特徴付けています．

IND-CCA1安全性をさらに拡張したものがIND-CCA2安全性です．IND-CCA1ゲームでは敵対者が復号オラクルと通信できるのは第一ステージだけでしたが，IND-CCA2ゲームでは第二ステージで識別すべき暗号文を受け取った後でも復号オラクルと通信を行うことができます．ただし挑戦者から受け取った暗号文は復号オラクルに渡すことはできません．

  • 第一ステージ
  1. 敵対者は任意の文字列を暗号文として復号オラクルに渡す．復号オラクルはskを使って復号した文章を敵対者に送り返す．このやりとりを敵対者は任意回繰り返す．
  • 第二ステージ
  1. 敵対者は二つのメッセージm_0とm_1を任意に選び，その両者を挑戦者に渡す．
  2. 敵対者は二つのメッセージm_0とm_1のどちらかを確率1/2づつで選び，公開鍵pkで暗号化する．その暗号文cを敵対者に渡す．
  3. 敵対者は挑戦者から受け取った暗号文c以外の任意の文字列を暗号文として復号オラクルに渡す．復号オラクルはskを使って復号した文章を敵対者に送り返す．このやりとりを敵対者は任意回繰り返す．
  4. 敵対者は挑戦者から受け取ったcがどちらのメッセージの暗号文かを当てる．もし当たれば敵対者の勝ち，外れれば敵対者の負け．

IND-CCA2ゲームではIND-CCA1ゲームとは異なり解読すべき暗号文が与えられた後でもその暗号文に関係した情報を復号オラクルから得られる可能性があります．