概要

線形暗号解析は、暗号の入力・出力・鍵のビットの間にあるアフィン関係（線形関係に定数を加えたもの）を探す暗号解析手法の一種である。主にブロック暗号に対して用いられるが、一部のストリーム系構成にも適用できる。暗号をブラックボックスとして扱い、ランダムなふるまいからの統計的なずれを利用して鍵ビットに関する情報を得る。暗号学の研究では、差分暗号解析と並ぶ主要な一般攻撃の一つとみなされている。

仕組み

この攻撃では、GF(2) 上の線形式――通常は、選択した平文ビット、暗号文ビット、鍵ビットの XOR 和――のうち、成り立つ確率がちょうど 1/2 からわずかにずれるものを見つける。多数の既知平文・暗号文対を集めることで、攻撃者はランダムからの偏りを測定し、それを利用して候補鍵を順位付けする。S-box（代入 बॉक्स）のような要素は、非ゼロの相関を生み出す近似を求める対象となる。複数ラウンドにまたがっていくつかの近似が組み合わさると、その偏りが増幅されることがあり、これを linear hull（線形ハル）と呼ぶ。実際の攻撃では、統計的仮説検定や鍵順位付けのヒューリスティックを用いて、最後に総当たり確認を行う前の有力な鍵ビットを絞り込むことが多い。線形手法は最も自然にブロック暗号へ適用されるが、他の構成へ向けた拡張もある。

歴史と発展

線形暗号解析の現代的な定式化は 1990 年代初頭に登場し、広く使われていた設計に実用的な弱点があることを示した研究によって広まった。その後、研究者たちはいくつもの改良を提案した。たとえば、複数の線形近似を組み合わせる方法、近似の重み付き和を用いる方法、非線形式を解析に取り入れる方法などである。また、派生手法やハイブリッド手法は、ストリーム暗号や多くのアルゴリズムのラウンド数を削減した版を対象にするようにも適応されてきた。

防御と実用上の考慮

線形攻撃が成功するには、通常は大量の既知平文または選択平文が必要であり、しかもその前提となる偏りは十分に小さくなければならない。そこで暗号設計者は、S-box における線形相関を最小化し、利用しやすい線形構造を崩す拡散層や鍵スケジュールを用い、経験的または理論的な耐性を示そうとする。新しい暗号が線形暗号解析に耐えることの証拠は、現代の設計評価において一般に求められる。

変種、重要性、区別

実際の線形暗号解析の運用では、しばしば複数の手法が組み合わされる。代表的な改良には次のようなものがある。

  • データ量の複雑さを下げるため、重み付き寄与を持つ複数の近似を用いる。
  • 多くの経路にわたって相関が蓄積する線形ハルを解析する。
  • 特定の暗号の特徴を狙うため、非線形の指示関数を組み込む。

線形暗号解析は統計的な既知平文型攻撃であり、代数的手法や総当たり法とは異なって、明示的な方程式を解くのではなく、ランダム性からの微小で体系的な逸脱を利用する。これは暗号の安全性を評価し比較するための中心的な道具であり、設計や標準化の文献では、参考文献や詳細な技術解説がしばしば引用される（暗号解析の概説や、暗号学リソースにあるアルゴリズム論文を参照）。

さらに入門的な説明や技術的な解説については、線形手法を他の解析アプローチと並べて扱う多くのサーベイ論文や教科書がある。実務者は、標準化文書や学術レビューに結び付いた資料を相互参照することが多い（ブロック暗号研究、ストリーム暗号の解説）。