シャノン研究ノート

シャノンの完全秘匿性：Communication Theory of Secrecy Systems に見る理想暗号の条件

Tags: 情報理論, 暗号理論, シャノン, 完全秘匿性, ワンタイムパッド

はじめに

クロード・シャノンの1948年の論文「A Mathematical Theory of Communication」は情報理論の基礎を築きましたが、その翌年の1949年に発表された論文「Communication Theory of Secrecy Systems」は、情報理論を暗号に応用する画期的な試みでした。この論文において、シャノンは暗号システムの秘匿性に関する情報理論的な枠組みを提示し、特に「理想的な暗号システム」、すなわち完全秘匿性 (Perfect Secrecy) の概念を初めて数学的に定義しました。本稿では、この完全秘匿性の定義とその情報理論的な意味、そしてシャノンが示したワンタイムパッド（Vernam Cipher）がなぜこの性質を満たすのかについて、専門家の視点から詳細に掘り下げていきます。

シャノンのこの研究は、それまで経験的・発見的手法が主であった暗号設計と解析に対して、厳密な数学的基盤を与えた点で極めて重要です。特に、暗号文を知っても平文に関するいかなる情報も漏洩しないという、直感的でありながら捉えどころのなかった「究極の安全性」を明確に定式化したことは、その後の情報理論的安全性という研究分野の出発点となりました。

完全秘匿性の情報理論的定義

シャノンは、理想的な暗号システムとは、盗聴者が暗号文 $C$ を観測しても、平文 $M$ について何も新しい情報を得られないシステムであると定義しました。これを確率論の言葉で表現すると、任意の平文 $m$ に対して、暗号文 $C$ が与えられた条件付き確率分布 $P(M=m | C=c)$ が、暗号文を知る前の平文の確率分布 $P(M=m)$ と変わらない、ということになります。すなわち、

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

この条件が任意の平文 $m$ と取りうる任意の暗号文 $c$ について成り立つとき、その暗号システムは完全秘匿性を満たすと言います。

情報理論の観点からは、この条件は平文 $M$ と暗号文 $C$ の間の相互情報量 $I(M; C)$ がゼロであることと等価です。相互情報量 $I(M; C)$ は、暗号文 $C$ を知ることによって平文 $M$ に関して得られる情報量を示し、次のように定義されます。

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

ここで、$H(M)$ は平文のエントロピー（不確かさ）、$H(M|C)$ は暗号文 $C$ が与えられた下での平文の条件付きエントロピーを示します。完全秘匿性の条件 $P(M=m | C=c) = P(M=m)$ は、暗号文 $C$ が与えられても平文の確率分布が変化しないことを意味するため、条件付きエントロピー $H(M|C)$ は平文のエントロピー $H(M)$ と等しくなります。

$$ H(M|C) = \sum_c P(C=c) H(M|C=c) $$ $$ H(M|C=c) = -\sum_m P(M=m|C=c) \log_2 P(M=m|C=c) $$ 完全秘匿性の条件 $P(M=m|C=c) = P(M=m)$ を代入すると、 $$ H(M|C=c) = -\sum_m P(M=m) \log_2 P(M=m) = H(M) $$ したがって、$H(M|C) = H(M)$ となり、$I(M; C) = H(M) - H(M) = 0$ が導かれます。これは、平文と暗号文が無相関であること、つまり暗号文から平文について何も統計的な情報を得られないことを意味します。

暗号システムのモデル

シャノンが解析した暗号システムは、以下の要素で構成されます。

正しく復号できるためには、任意の $m \in \mathcal{M}$ と $k \in \mathcal{K}$ に対して、$D_k(E_k(m)) = m$ が成り立つ必要があります。 また、シャノンのモデルでは、平文 $M$ は確率変数であり、その確率分布 $P(M)$ は盗聴者にも既知であると仮定されます。鍵 $K$ も確率変数であり、その確率分布 $P(K)$ は通常、暗号システムの設計者が定めるものです。平文 $M$ と鍵 $K$ は互いに独立であると仮定します。暗号文 $C$ は、$C = E_K(M)$ として生成される確率変数です。

ワンタイムパッドと完全秘匿性

シャノンは、ワンタイムパッド（Vernam Cipher）が完全秘匿性を満たす最も単純な例であることを示しました。ワンタイムパッドは、平文、暗号文、鍵が同じサイズのバイナリベクトルであり、暗号化と復号化がビットごとのXOR演算によって行われるシステムです。

平文 $M = (m_1, m_2, \dots, m_n)$ 鍵 $K = (k_1, k_2, \dots, k_n)$ 暗号文 $C = (c_1, c_2, \dots, c_n)$

ここで、$m_i, k_i, c_i \in {0, 1}$ です。 暗号化: $c_i = m_i \oplus k_i$ （$\oplus$ はXOR演算） 復号化: $m_i = c_i \oplus k_i$ （XORは自身との演算で元に戻るため、$c_i \oplus k_i = (m_i \oplus k_i) \oplus k_i = m_i \oplus (k_i \oplus k_i) = m_i \oplus 0 = m_i$）

ワンタイムパッドが完全秘匿性を満たすための重要な条件は、以下の通りです。 1. 鍵空間のサイズ $|\mathcal{K}|$ が平文空間のサイズ $|\mathcal{M}|$ 以上であること。（バイナリベクトルの場合、鍵の長さが平文の長さと同じであること） 2. 鍵 $K$ が鍵空間 $\mathcal{K}$ 上で一様ランダムに選択され、かつ平文 $M$ と統計的に独立であること。 3. 各鍵は一度だけ使用されること。

ワンタイムパッドが完全秘匿性を満たすことの証明

鍵 $K$ が鍵空間 $\mathcal{K}$（$|\mathcal{K}| = |\mathcal{M}| = N$ と仮定）上で一様ランダムであり、$M$ と独立であるとします。つまり、$P(K=k) = 1/N$ for all $k \in \mathcal{K}$。

任意の平文 $m \in \mathcal{M}$ と任意の暗号文 $c \in \mathcal{C}$ について、$P(M=m | C=c) = P(M=m)$ を示すことが目標です。

条件付き確率の定義より、$P(M=m | C=c) = \frac{P(C=c | M=m) P(M=m)}{P(C=c)}$ です。 完全秘匿性を示すには、これが $P(M=m)$ と等しいこと、つまり $P(C=c | M=m) = P(C=c)$ を示すことが必要十分です。これは平文と暗号文が統計的に独立であることと同値です。

$C = E_K(M)$ ですから、$C=c$ となるのは、$E_K(M)=c$ となる鍵 $K$ が選ばれた場合です。 平文 $M=m$ が固定されたとき、暗号文 $C=c$ となる鍵 $k$ は、暗号化操作の可逆性から一意に定まります。具体的には、$k = D_c(m)$ となります。（XOR暗号の場合は $k = m \oplus c$）。 したがって、$P(C=c | M=m) = P(E_K(m) = c | M=m)$ ですが、$E_K(m)=c$ となるのは鍵 $K$ が $k = D_c(m)$ に等しい場合のみなので、 $P(C=c | M=m) = P(K = D_c(m) | M=m)$ となります。

ここで、鍵 $K$ は平文 $M$ と独立であるという仮定を使用します。 $P(K = D_c(m) | M=m) = P(K = D_c(m))$ です。 鍵 $K$ は鍵空間 $\mathcal{K}$ 上で一様ランダムに分布しているので、$P(K=k) = 1/|\mathcal{K}|$ for all $k \in \mathcal{K}$ です。 平文空間 $\mathcal{M}$、暗号文空間 $\mathcal{C}$、鍵空間 $\mathcal{K}$ のサイズが全て $N$ で等しいワンタイムパッドの場合、任意の $(m, c)$ ペアに対して、それを結びつける鍵 $k=m \oplus c$ は必ず鍵空間 $\mathcal{K}$ の要素となります。 したがって、$P(K = D_c(m)) = 1/|\mathcal{K}| = 1/N$ となります。 よって、$P(C=c | M=m) = 1/N$ です。

次に、$P(C=c)$ を計算します。これは周辺確率であり、平文の全ての可能性について和をとることで得られます。 $P(C=c) = \sum_{m \in \mathcal{M}} P(C=c | M=m) P(M=m)$ 先ほど求めた $P(C=c | M=m) = 1/N$ を代入します。 $P(C=c) = \sum_{m \in \mathcal{M}} \frac{1}{N} P(M=m) = \frac{1}{N} \sum_{m \in \mathcal{M}} P(M=m)$ 平文の確率分布は正規化されているので、$\sum_{m \in \mathcal{M}} P(M=m) = 1$ です。 したがって、$P(C=c) = 1/N$ となります。

これで、$P(C=c | M=m) = 1/N$ と $P(C=c) = 1/N$ が示されました。 任意の $m, c$ に対して $P(C=c | M=m) = P(C=c)$ が成り立つため、完全秘匿性の条件 $P(M=m | C=c) = P(M=m)$ も成り立ちます。

この証明からわかるように、完全秘匿性が成立するためには、鍵の数が少なくとも平文の数と同じである必要があり ($|\mathcal{K}| \ge |\mathcal{M}|$)、かつ、どの平文 $m$ からどの暗号文 $c$ へも、鍵空間 $\mathcal{K}$ 内の少なくとも一つの鍵で到達可能である必要があります。そして、その鍵が一様ランダムに選ばれる必要があります。ワンタイムパッドは、鍵空間と平文空間のサイズが同じで、各平文と各暗号文のペアが一意の鍵で結ばれるため、この条件を満たすのです。

歴史的背景と意義

シャノンの完全秘匿性の概念は、第二次世界大戦中の暗号研究に端を発しています。彼はベル研究所で暗号関連の研究に従事しており、物理的な暗号装置やシステムの解析を行っていました。その経験から、暗号の「安全性」を数学的に定義し、解析することの重要性を認識しました。

それまでの暗号学では、シーザー暗号やヴィジュネル暗号のような換字式・転置式暗号が主流であり、その安全性評価は経験的な頻度分析に頼るところが大きかったです。シャノンは、情報理論の枠組みを用いることで、盗聴者が利用できる情報（暗号文、通信システムの統計的性質、平文の統計的性質など）と、システムが提供する秘匿性との関係を定量的に分析できることを示しました。

完全秘匿性は、理論的な究極の安全性を提供しますが、その実用には大きな課題があります。それは、鍵の長さが平文と同じである必要があり、かつその鍵を安全に一度だけ共有しなければならないという点です（鍵配送問題）。これは、大量のデータを秘匿通信する際には非常に非効率です。しかし、この概念は、その後に続く計算量的安全性 (Computational Security) の研究にとって重要な指標となりました。計算量的安全性は、無限の計算能力を持つ盗聴者に対しては安全ではないかもしれないが、現実的な計算能力を持つ盗聴者にとっては解読が困難である、という考え方に基づいています。

現代における位置づけと限界

シャノンの完全秘匿性は、現代暗号理論においても非常に重要な概念です。特に、理論的な安全性を議論する上での理想形として参照されます。例えば、量子暗号における鍵配送プロトコルは、理論的には盗聴不可能な方法で鍵を共有することを目的としており、これにより完全秘匿性を持つワンタイムパッドの実用化を目指す研究が進められています。

また、完全秘匿性は、情報理論的安全性を持つ他の暗号プリミティブ（例：秘密分散法）の研究においても基本的な考え方を提供しています。

しかし、完全秘匿性の定義は平文の確率分布が既知であるという仮定に基づいています。実際には、平文の統計的性質を完全に把握することは困難な場合が多く、また、盗聴者は平文に関する事前情報（例えば、通信は英語のテキストである、特定の定型文が含まれる可能性が高いなど）を利用して攻撃を行う可能性があります。シャノンの論文では、このような事前情報の影響や、鍵が一度きりではなく繰り返し使用された場合（ユニシティ距離の概念など）についても詳細に論じられており、これらは現代の暗号解析においても基礎的な考え方となっています。

結論

クロード・シャノンが「Communication Theory of Secrecy Systems」で導入した完全秘匿性の概念は、暗号システムの情報理論的な安全性に関する最初の厳密な定義でした。暗号文から平文に関するいかなる情報も得られないというこの理想的な安全性は、平文と暗号文の間の相互情報量がゼロであることと同値であり、ワンタイムパッドがこの性質を満たすことが証明されました。

シャノンの研究は、暗号理論に数学的基礎を与え、情報理論的安全性という新しい研究分野を切り開きました。完全秘匿性は、その実用上の制約から広く利用されているわけではありませんが、理論的な安全性の benchmark として、また現代暗号が目指す計算量的安全性や、量子鍵配送のような新しい技術の理論的背景として、今日でもその重要性は失われていません。シャノンのこの論文は、情報理論が通信だけでなく、秘匿性という全く異なる側面にも応用できることを示した古典であり、情報科学分野の研究者にとって、その核心部分を深く理解する価値は計り知れません。