今まで安永先生の「暗号理論入門」第１章、第２章をベースに完全秘匿性を中心とした暗号の安全性について勉強してきました。ここから先はいよいよ計算量的安全性の話に入ります。
完全秘匿性を持つ暗号には「鍵空間のサイズは平文空間のサイズと同じかより大きい」という性質があります。鍵や平文をビット列で表すとすると、この事実は「鍵長は平文と同じかより長い」ということになります。また同じ鍵で複数の平文を暗号化して送ると完全秘匿性が失われることも証明しました。
共通鍵暗号を使って通信を行う前に事前に鍵を共有する必要がありますが、完全秘匿性を得ようとするとその際以下を保つ必要があります。
- 送りたい平文と同じかそれ以上の長さの鍵を作って事前に共有する必要がある。
- １度使った鍵は破棄することにする。暗号文を作る際には未使用の鍵を使う。
これらは実際に暗号運用を行う際に大きな障害となります。完全秘匿性を持つ暗号(ワンタイムパッド暗号)は極めて重要な通信（Wikipediaによれば冷戦時の米ソホットラインなど）で使われたそうです。
短い鍵を使うことを許した場合、暗号の実用性は大幅に向上します。その場合に完全秘匿性は失われますが、代わりにどのような安全性を考えることができるのか、ということが計算量的安全性という形で研究されてきました。
安永さんの書籍で言えば第３章からは計算量的安全性の話に入ります。
完全識別不可能性の定義を振り返ります。2つの平文m0, m1についてどちらかを暗号化した暗号文cが観測されたとします。cを見た上で、その平文がm0である確率とm1である確率が「同じ」であることが完全識別不可能性の定義でした。
計算量的識別不可能性では、計算量εを設定して、それぞれの確率が計算量εでは識別できない、という形に変更になります。εを、鍵長をパラメータとする関数とみなせば漸近的な議論もできます。これ自体は分かりやすい変更だと思いました。
一方第４章では確率分布の（計算量的）識別不可能性を定義し、ランダムと擬似ランダムを定義し、この擬似ランダムを使うと、短い鍵も長い擬似ランダムに伸長することで計算量的に安全に暗号化に使えることが示されます。擬似ランダムの意味と重要性がわかる面白い章です。
引き続きLean4で定義と証明を形式化しながらこちらで紹介していこうと思います。
