シャノン研究ノート

シャノン「Communication Theory of Secrecy Systems」における鍵エントロピーと完全秘匿性の情報理論的解析

Tags: 情報理論, 暗号理論, セキュリティ, シャノンエントロピー, 完全秘匿性, CommunicationTheoryOfSecrecySystems

序論：情報理論による暗号解析の扉を開く

クロード・シャノンが1948年に発表した記念碑的な論文『A Mathematical Theory of Communication』は、その第5部「The Secret Systems」において、情報理論を暗号学へと応用する先駆的な試みを行いました。これは、それまでの経験則や直感に頼りがちであった暗号の安全性評価に、初めて厳密な数学的枠組みを導入する画期的なものでした。本記事では、この第5部に焦点を当て、シャノンが提示した暗号システムの通信理論的モデル、特に「鍵のエントロピー」の概念と「完全秘匿性（Perfect Secrecy）」の定義、そしてそれを達成するための情報理論的な条件について、深く掘り下げて解説いたします。

シャノンのアプローチは、暗号システムを通信路として捉え、送信者（アリス）が平文を、受信者（ボブ）が暗号文を通じて平文を復元しようとするプロセスを、情報理論の観点から分析するというものでした。ここに盗聴者（イブ）が登場し、暗号文から平文や鍵に関する情報を得ようとします。情報理論は、この情報漏洩の可能性を定量的に評価する強力なツールを提供しました。ターゲット読者である情報科学分野の研究者の皆様にとって、シャノンのこの仕事は、現代暗号理論の情報理論的安全性の基盤を理解する上で不可欠なものです。

暗号システムの通信理論的モデル

シャノンは、暗号システムを以下のような要素から構成される情報通信システムとしてモデル化しました。

  1. 情報源 (Source): 平文メッセージ $M$ を生成します。メッセージはアルファベット $\mathcal{M}$ から取られ、確率分布 $P(M=m)$ に従います。
  2. 暗号化装置 (Encoder): 平文 $M$ と鍵 $K$ を用いて、暗号文 $C$ を生成します。暗号化は通常、関数 $E: \mathcal{M} \times \mathcal{K} \to \mathcal{C}$ によって行われます。ここで $\mathcal{K}$ は鍵空間、$\mathcal{C}$ は暗号文空間です。鍵 $K$ もまた、鍵空間 $\mathcal{K}$ 上の確率分布 $P(K=k)$ に従う確率変数とみなされます。鍵は平文とは独立に選択されると仮定されることが多いですが、シャノンの議論ではより一般的な場合も考慮されます。
  3. 通信路 (Channel): 暗号文 $C$ が送信される媒体です。盗聴者はこの通信路を傍受し、暗号文 $C$ を得ることができます。
  4. 復号化装置 (Decoder): 暗号文 $C$ と（正しい）鍵 $K$ を用いて、元の平文 $M'$ を復元します。復号化は通常、関数 $D: \mathcal{C} \times \mathcal{K} \to \mathcal{M}$ によって行われます。正しく復号できるシステムでは、$D(E(m, k), k) = m$ が成り立ちます。
  5. 盗聴者 (Eve): 暗号文 $C$ を傍受し、そこから平文 $M$ に関する情報を抽出しようとします。盗聴者は通常、暗号化・復号化のアルゴリズムは知っているが、送信に使われた鍵 $K$ は知らないと仮定されます。

このモデルにおいて、システム全体の振る舞いは、平文 $M$、鍵 $K$、暗号文 $C$ という3つの確率変数によって特徴づけられます。特に、これらの確率変数間の統計的依存関係が、システムの安全性（秘匿性）を評価する鍵となります。

鍵のエントロピーと完全秘匿性の定義

シャノンは、システムの秘匿性を定量化するために情報理論のエントロピーと相互情報量の概念を導入しました。

鍵 $K$ の不確かさは、そのエントロピー $H(K) = -\sum_{k \in \mathcal{K}} P(k) \log_2 P(k)$ によって測られます。鍵のエントロピーが大きいほど、盗聴者が鍵を特定することは困難になります。

暗号システムにおける究極の安全性として、シャノンは完全秘匿性 (Perfect Secrecy) を定義しました。

定義（完全秘匿性）

暗号システムが完全秘匿性を持つとは、暗号文 $C$ を観察しても、平文 $M$ に関するいかなる情報も漏洩しないことである。情報理論的には、これは平文 $M$ と暗号文 $C$ の間の相互情報量 $I(M; C)$ がゼロであることと同値です。

$$ I(M; C) = H(M) - H(M|C) = 0 $$

ここで $H(M)$ は平文のエントロピー、$H(M|C)$ は暗号文 $C$ を観測した後の平文の条件付きエントロピーです。$I(M; C) = 0$ という条件は、$H(M|C) = H(M)$ と同値であり、これは暗号文を知っても平文に関する不確かさが全く減少しないことを意味します。

また、相互情報量の別の定義 $I(M; C) = H(C) - H(C|M)$ から、$I(M; C)=0$ は $H(C|M) = H(C)$ とも同値です。これは、平文を知っていても暗号文の不確かさが減少しないことを意味します。通常、暗号化関数は決定論的であるため、$C$ は $M$ と $K$ が与えられれば一意に決まります。すなわち $H(C|M, K) = 0$ です。したがって、$H(C|M) = H(E(M, K)|M) = H(K|M)$ となります。平文と鍵が独立であると仮定する場合、$H(K|M) = H(K)$ であるため、$H(C|M) = H(K)$ となります。この場合、$I(M;C)=0$ は $H(C) = H(K)$ を意味します。

さらに、完全秘匿性の定義は、確率論的には以下のようにも表現できます。

$$ P(M=m | C=c) = P(M=m) \quad \text{for all } m \in \mathcal{M}, c \in \mathcal{C} $$

これは、任意の暗号文 $c$ が与えられた条件下での平文 $m$ の事後確率が、暗号文を知らない場合の事前確率と変わらないことを意味します。ベイズの定理 $P(m|c) = \frac{P(c|m)P(m)}{P(c)}$ を用いると、この条件は $P(c|m)P(m) = P(m)P(c)$、すなわち $P(c|m) = P(c)$ と同値になります（ただし $P(m) > 0$）。これは、特定の平文 $m$ が与えられた条件下での暗号文 $c$ の発生確率が、平文に関わらず一定であるということを意味します。

完全秘匿性を達成するための条件

シャノンは、この完全秘匿性を達成するためにシステムが満たすべき情報理論的な条件を導出しました。最も重要な結果の一つは、平文空間と鍵空間のサイズに関するものです。

シャノンの定理（完全秘匿性の条件）

有限の平文空間 $\mathcal{M}$ と鍵空間 $\mathcal{K}$ を持つ暗号システムにおいて、任意の平文分布に対して完全秘匿性を達成するためには、鍵空間のサイズ $|\mathcal{K}|$ が平文空間のサイズ $|\mathcal{M}|$ 以上である必要があり、すなわち $|\mathcal{K}| \ge |\mathcal{M}|$ が満たされなければならない。さらに、鍵が平文から独立しており、$|\mathcal{K}| = |\mathcal{M}|$ かつ鍵が一様分布に従う場合に、完全秘匿性が達成可能である。

この定理の証明の核心部分に触れてみましょう。 完全秘匿性の条件 $P(c|m) = P(c)$ は、行列形式で考えることができます。平文 $m_i$ と鍵 $k_j$ から暗号文 $c_{ij}$ が生成されるとすると、$P(c|m)$ は、各行が特定の平文 $m_i$ に対応し、各列が特定の暗号文 $c$ に対応する、条件付き確率の行列とみなせます。$P(c|m) = P(c)$ は、この行列の全ての行が同じ確率分布（暗号文の周辺確率分布 $P(c)$）であることを意味します。

また、任意の平文 $m$ に対し、$P(C=c|M=m) = \sum_{k: E(m,k)=c} P(K=k|M=m)$ です。平文と鍵が独立であれば、$P(K=k|M=m) = P(K=k)$ となります。

完全秘匿性が成立するためには、任意の平文 $m$ と任意の暗号文 $c$ の組み合わせについて、$P(C=c|M=m) > 0$ となる鍵 $k$ が少なくとも一つ存在する必要があります。なぜなら、$P(c|m)=P(c)$ であり、完全秘匿性を持つシステムでは全ての起こりうる暗号文 $c$ に対して $P(c)>0$ でなければならないからです（そうでなければ、特定の暗号文の出現から平文について何らかの情報が得られてしまう）。もし $P(C=c|M=m)=0$ となる $(m, c)$ の組が存在すれば、$P(c)=0$ となり完全秘匿性に反します。 したがって、任意の $m \in \mathcal{M}$ と $c \in \mathcal{C}$ に対して、$E(m, k) = c$ となる鍵 $k \in \mathcal{K}$ が存在しなければなりません。これは、全ての平文 $m$ から全ての暗号文 $c$ へのマッピングが、鍵の選択によって可能でなければならないということです。

これは、暗号化関数 $E_k(\cdot) = E(\cdot, k)$ を写像 $E_k: \mathcal{M} \to \mathcal{C}$ と見たとき、任意の $m \in \mathcal{M}$ と $c \in \mathcal{C}$ に対して、$c = E_k(m)$ となる $k \in \mathcal{K}$ が存在することを含意します。特定の平文 $m$ を固定したとき、生成されうる暗号文の集合は ${E_k(m) | k \in \mathcal{K}}$ です。完全秘匿性を持つためには、この集合が全ての可能な暗号文の集合 $\mathcal{C}$ と一致しなければなりません。したがって、任意の $m \in \mathcal{M}$ に対して $|{E_k(m) | k \in \mathcal{K}}| = |\mathcal{C}|$ となる必要があります。これは $|\mathcal{K}| \ge |\mathcal{C}|$ を示唆します。また、正しく復号できるためには、任意の鍵 $k$ に対して $E_k$ が単射である必要があります（異なる平文が同じ暗号文に写されると、復号時に区別できなくなるため）。つまり、任意の鍵 $k$ について $|E_k(\mathcal{M})| = |\mathcal{M}|$ です。生成されうる暗号文は ${E_k(m)}$ の和集合に含まれるので、 $|\mathcal{C}| \le \sum_{k \in \mathcal{K}} |E_k(\mathcal{M})| = |\mathcal{K}| \cdot |\mathcal{M}|$ となりますが、完全秘匿性の条件からはより厳しい制約が導かれます。

任意の平文 $m$ に対して $P(c|m)=P(c)$ が成り立ち、また任意の鍵 $k$ に対して $m \mapsto E(m,k)$ が単射であると仮定すると、各鍵 $k$ は平文空間 $\mathcal{M}$ から暗号文空間 $\mathcal{C}$ への $|\mathcal{M}|$ 個の要素を写像します。 もし $|\mathcal{M}| > |\mathcal{C}|$ であれば、鳩ノ巣原理により、どのような鍵を用いても単射な写像を構成することは不可能であり、復号が一意に行えなくなります。したがって、正しく復号できるシステムでは $|\mathcal{M}| \le |\mathcal{C}|$ でなければなりません。 シャノンの定理の核心は、$|\mathcal{K}| \ge |\mathcal{M}|$ という条件が完全秘匿性のために必要であることの証明にあります。これは、平文空間よりも小さい鍵空間では、原理的に完全秘匿性は達成できないことを意味します。

さらに、鍵が一様分布 $P(K=k) = 1/|\mathcal{K}|$ に従い、$|\mathcal{K}| = |\mathcal{M}| = |\mathcal{C}|$ の場合、特に $|\mathcal{K}| = |\mathcal{M}|$ かつ、各平文 $m$ と暗号文 $c$ のペア $(m, c)$ に対して、それを満たす鍵 $k$ がちょうど一つ存在する場合、$P(c|m)$ は以下のようになります。 $P(C=c|M=m) = \sum_{k: E(m,k)=c} P(K=k)$. もし任意の $(m, c)$ ペアに対してそれを満たす $k$ がちょうど一つ存在し、鍵が一様分布であれば、$P(K=k) = 1/|\mathcal{K}| = 1/|\mathcal{M}|$ となります。 したがって、$P(C=c|M=m) = 1/|\mathcal{M}|$. 一方、暗号文 $c$ の周辺確率 $P(c)$ は、平文 $m$ の確率分布 $P(m)$ を用いて $P(c) = \sum_{m \in \mathcal{M}} P(c|m) P(m)$ と書けます。 もし $P(c|m)$ が全ての $m$ について一定の値（例えば $1/|\mathcal{M}|$）であれば、$P(c) = \sum_{m \mathcal{M}} (1/|\mathcal{M}|) P(m) = (1/|\mathcal{M}|) \sum_{m \in \mathcal{M}} P(m) = 1/|\mathcal{M}|$ (ただし $\sum P(m) = 1$)。 このとき、$P(c|m) = 1/|\mathcal{M}|$ と $P(c) = 1/|\mathcal{M}|$ が一致し、$P(c|m) = P(c)$ が成り立ちます。 この条件、すなわち任意の $(m, c)$ ペアに対して $E(m, k) = c$ となる鍵 $k$ がちょうど一つ存在するシステムは、置換暗号（特定の平文に対応する鍵が一つずつ存在する）かつ鍵が一様分布である場合に実現されます。最も典型的な例が、鍵空間、平文空間、暗号文空間のサイズが等しく、かつ鍵が各平文を各暗号文にランダムにマッピングするようなシステムです。

この理論的な構成を満たす具体的な例が、ワンタイムパッド (One-Time Pad) です。これは、平文、鍵、暗号文が全て同じサイズ（ビット数）を持ち、暗号化がビットごとのXORによって行われるシステムです。鍵が平文と同じサイズで、かつ鍵空間全体から独立かつ一様ランダムに選ばれ、一度しか使用されない場合、ワンタイムパッドは完全秘匿性を達成します。

発表当時の背景と歴史的意義

シャノンが情報理論的な暗号解析を発表した背景には、第二次世界大戦中の暗号研究があります。彼はベル研究所で暗号研究に関わっており、その経験がこの理論の構築に影響を与えたと考えられています。当時の暗号学は、特定の暗号方式に対する破読の試みとその回避策という形で発展しており、安全性に関する一般的な理論的基盤は確立されていませんでした。

シャノンの貢献は、暗号の安全性を「情報がどれだけ漏れるか」という観点から厳密に定義し、定量化する道を開いた点にあります。完全秘匿性という概念は、どのような暗号システムが理論的に破読不可能であるかを示し、安全性の評価に客観的な基準をもたらしました。鍵空間のサイズが平文空間のサイズを下回ってはならないという結論は、鍵の長さがセキュリティ強度に直接的に影響することを明確に示しました。これは、現代暗号における鍵長の設計思想の根幹にも通じる考え方です。

現代における位置づけと応用

シャノンの完全秘匿性の概念は、現代暗号学における「情報理論的安全性（Information-Theoretic Security）」という分野の基礎を築きました。これは、計算能力に限界がない攻撃者に対しても安全性を保証する、最も強力な安全性の概念です。

しかしながら、シャノンの定理が示すように、完全秘匿性を達成するためには鍵長が平文長以上である必要があり、さらに鍵を完全にランダムかつ一度しか使わないという制約があります。これは、ワンタイムパッドのように理論的には究極の安全性を持つ一方で、現実世界の多くの通信においては鍵管理のコストや使い捨ての制約から実用的ではありません。

このため、現代暗号学の主流は、計算能力に限界がある攻撃者に対して安全性を保証する「計算量的安全性（Computational Security）」に移っています。RSAやAESのような公開鍵暗号や共通鍵暗号は、情報理論的には安全ではありませんが、現在の計算技術では破読が事実上不可能であると期待される計算困難な問題を基礎としています。

それでもなお、シャノンの情報理論的アプローチは、現代暗号においても重要な役割を果たしています。例えば、

シャノンが定義した暗号システムの通信理論的モデルと完全秘匿性という概念は、現代の暗号学の研究者にとって、安全性の本質を理解し、異なる安全性の概念（情報理論的 vs 計算量的）を比較検討する上で不可欠な出発点となっています。

結論

クロード・シャノンによる『A Mathematical Theory of Communication』第5部における暗号システムの通信理論的解析は、情報理論を暗号学に応用する最初の試みであり、その後の暗号学の発展に計り知れない影響を与えました。彼が導入した鍵のエントロピーという概念や、完全秘匿性という明確な安全性の定義は、暗号の安全性に関する議論に厳密な数学的基礎をもたらしました。

特に、完全秘匿性を達成するためには鍵長が平文長以上である必要があり、鍵が一様かつ独立である場合にそれが可能であるというシャノンの定理は、ワンタイムパッドの理論的安全性を示すとともに、現実的な暗号システム設計における鍵管理の課題を浮き彫りにしました。情報理論的安全性という究極の目標は、計算量的安全性を追求する現代暗号学の主流とは異なりますが、その理論的基盤は今日もなお、情報理論的安全性を持つシステムの設計や、あらゆる暗号技術の安全性の根本的な限界を理解する上で、極めて重要な示唆を与え続けています。シャノンのこの独創的な仕事は、情報科学、通信理論、そして暗号学の交差点における、時代を超えた古典として位置づけられるべきでしょう。