これから数回にわたって「セキュリティを数学的に証明する」話を書いていきます。自分の勉強のための覚書みたいなものですし、まだ勉強を始めたばかりの分野なので記載に間違いがあるかもしれません。そもそも理解の方向性が間違っているかもしれません。決して鵜呑みにしないようにしてください。
テキストとしてはとりあえず、
を購入して読んでいます。この本の著者が公開しているPDFも参考にしています。
https://tcc.c.titech.ac.jp/yasunaga/appmath6/perfect.pdf
数学とセキュリティの間には重要な接点があります。証明可能安全性と呼ばれる分野で主に暗号アルゴリズムやセキュア通信プロトコルの安全性を数学的に証明する、という分野です。長くセキュリティの仕事をしていると当然このような考え方(例えばCommon Criteria のEAL7)に接する機会もありますが、今まできちんと勉強したことはありませんでした。
暗号の安全性の数学的証明の歴史を遡ると、クロードシャノンの有名な論文
A Mathematical Theory of Cryptography
にたどり着きます。後で詳しく述べますが、シャノンはこの論文で確率論の議論を利用して安全性を定式化しています。少しだけその様子を紹介します。攻撃者が暗号で使われている鍵を取ることを考えましょう。128bitの鍵を出鱈目に１つ選ぶと正解に当たる確率は$\frac1{2^{128}}$です。もし暗号文を知って（それを解析することで）鍵の候補を絞り込めればこの確率をより大きくすることができます。そしてこの確率が$1$に十分近ければ暗号文の解析から鍵を取ることができたことになります。
暗号の安全性を数学的に証明する際にはセキュリティの中でも最も厳密な議論を行ないます。まず安全性を数学的に定義します。また暗号やプロトコルの記述を厳密に行います。そして想定されうる攻撃方法を定式化します。そして想定した攻撃に対して安全であることを安全性の定義に沿って証明します。
実はそいうことも今回初めて知りました。ここからわかることは「未知のどんな攻撃にも安全であることを証明しているわけではない」ということです。既知の攻撃に対して安全であることを証明しているのです。既知のすべての攻撃に対して安全な暗号であっても、新しい攻撃が見つかればその攻撃に耐えられるかどうかは改めて証明が必要です。そして攻撃が成功することがわかればその暗号は危殆化（安全な暗号ではなくなった）します。
クロードシャノンの論文では（一種理想的な）安全性の定義として「完全秘匿性」という概念を数学的に定義しています。そして完全秘匿性を持つ暗号のいくつかの性質を導いています。暗号解読は暗号文を入手して平文（あるいは鍵）を入手することです。そこで上述の確率の概念を使うと次のように安全性の定式化ができます。
完全秘匿性：暗号文を知る前に正しい平文を得られる確率と暗号文を知って正しい平文が得られる確率が等しい時、この暗号は完全秘匿性を持つ、と言われます。
数学的な定義は以上なのですが、これがどんな状況をモデル化しているかを理解することが重要です。実際の暗号解読（軍事機関や諜報機関がやる仕事）は暗号文を入手してそれを解析することで平文に辿り着くことです。つまり暗号文から何らかの平文や鍵に関する情報が漏洩していることを見つけます。最も初等的なものとして平文が英語ならアルファベットの出現頻度が暗号文に影響を与えることなどです。このわずかな情報を元に軍事機関や諜報機関が持つ莫大な計算機のリソースを投入して平文や鍵を得る、というのが暗号解読なのです。
しかしながら暗号文に元の平文や鍵に関する情報が全く含まれていない場合にはどんなに賢い暗号学者であってもどれだけ計算機をぶん回しても平文や鍵にたどり着くことは出来ません。つまりこの暗号では平文や鍵は暗号文から完全に秘匿されている、という安全性があるわけです。
この状況を数学的によくわかっている確率を道具に使い、「暗号文を知らずに平文を得る確率」と「暗号文を知って平文を得る確率」に帰着させたのが上記の完全秘匿性という安全性の定義なのです。
先の説明の中で「どれだけ計算機をぶん回しても平文や鍵に辿り着けない」と書きました。無制限の計算資源と時間（計算時間）を持ってしても破れない、という性質も完全秘匿性ではうまくモデル化されています。このような性質を「情報理論的安全性」と呼びます。この条件を弱めると計算量的安全性という考えにたどり着きます。それについては別の回に述べます。
次回は少し数式を用いて完全秘匿性及びそれと同値な定義を紹介します。また完全秘匿性を持つ具体的な暗号としてワンタイムパッド暗号を紹介します。
