書記が数学やるだけ#871 暗号における完全秘匿性

共通鍵暗号を考えるにあたり，暗号における完全秘匿性について確認しておく。

問題

説明

一般的な暗号方式は，鍵生成アルゴリズムGen，暗号化アルゴリズムEnc，復号アルゴリズムDecからなる三つ組アルゴリズム(Gen, Enc, Dec)として記述できる。

共通鍵暗号系は，暗号化と復号に同一の鍵を用いる暗号方式であり，ブロック暗号に分類されるIDEA，AES，Camelliaや，ストリーム暗号に分類されるRC4，MUGIが挙げられる。

暗号が満たすべき性質のうち，正当性は「正しく計算された暗号文からは元の平文が復元できる」ことを示している。また，19世紀にアウグスト・ケルクホフス（Auguste Kerckhoffs）によって提案されたケルクホフスの原理では，「暗号方式は，秘密鍵以外の全てが公知になったとして，なお安全であるべきである」と示されており，シャノンはこれを「敵はシステムを知っている」("the enemy knows the system")という簡潔な言葉で表現した。

秘匿性とは「暗号文から平文に関する情報が得られない」ことで，シャノンは完全秘匿性について以下の定式化を行なった。

また，完全秘匿性は完全識別不可能性や完全模倣性と同値である。

バーナム暗号は，ギルバート・バーナムが発明した，排他的論理和を用いた暗号機械システムおよびその暗号方式（機械式暗号）であり，シャノンはこれを情報理論的安全性を満たす例として取り上げた。しかし，通信量と同量の秘密情報をあらかじめ共有する必要がある点，また運用上は同期がズレる可能性が問題となり，ごく特殊な目的でしか使用されなかったものと考えられている。

解答

まず完全秘匿性と完全識別不可能性の同値を示す。

導出には確率の独立性や全確率の定理などを用いる。

完全識別不可能性と完全模倣可能性の同値については以下の通り。

「完全秘匿な暗号は，平文以上の長さの鍵を要する」ことを背理法から示す。このことから，完全秘匿であることは暗号化に多大なコストを要することがわかる。

完全秘匿の例としてバーナム暗号を取り上げる，ここでは完全識別不可能性から示している。

一方で，2文字以上のシーザー暗号は，完全識別不可能性でないため完全秘匿でない。

本記事のもくじはこちら：