書評

森山大輔・西巻陵・岡本龍明「公開鍵暗号の数理」（シリーズ応用数理 2巻）

現代暗号理論では、公開鍵暗号やディジタル署名などの暗号要素技術には安全性の厳密な定義(定式化)がされ、さらに具体的な方式に対しては厳密な安全性の証明が与えられることが必須となっている。安全性の証明は、「ある計算問題(例えば巨大な2つの素数の積の素因数分解)を現実的な計算資源(実行時間・メモリなど)で解くことが困難ならば、その暗号技術の安全性を現実的な計算資源で破る攻撃方法(攻撃アルゴリズム)は存在しない」ことを数学的に証明することによって行われる。しかし、そのような安全性の定義や証明には、暗号理論に独特の方法論や論法を用いるため、非専門家が、安全性定義の意味や安全性証明の内容を正しく理解することは、必ずしも容易ではない。

本書は、公開鍵暗号を中心に、現代暗号理論における暗号要素技術の安全性の定式化、効率的な方式の構成法、厳密な安全性証明手法などを、初学者でも容易に理解できるように平易に紹介することを目的として書かれた教科書である。

本書は全8章で構成されている。3章以降の内容は独立性が高く、前提となる定義・定理などへのポインターが適宜置かれているため、興味のある章を読み進め、必要に応じて前後に書かれた定義や定理を参照する、という読み方もできる。各章の主な内容は以下の通りである：

第1章「数学的準備」では、本書で取り扱う暗号技術の定義や方式を理解するための、代数学、整数論、確率、計算量理論それぞれの数学的準備が行われる。

第2章「安全性証明における基本概念」では、現代暗号理論における、暗号要素技術の安全性定義や安全性証明のための基本的な概念が説明される。また、2000年代以降主流の安全性証明技法であるゲーム変換法も説明されている。

第3章「基礎理論」では、より上位の暗号技術の構成要素として頻繁に用いられる一方向性関数、擬似乱数生成器、擬似ランダム関数などの要素技術の定義及び構成法、相互関係が説明されている。特に、計算困難性と識別不可能性の架け橋となるGoldreich-Levin定理や、擬似乱数生成器を用いた擬似ランダム関数の構成法など、暗号理論のマイルストーンとなる重要な成果の証明が示されている。

第4章「共通鍵暗号」では、共通鍵暗号、メッセージ認証子、ハッシュ関数などの”共通鍵系”の暗号要素技術の安全性定義や基礎的な構成法が紹介されている。

第5章「公開鍵暗号の安全性」では、公開鍵暗号の安全性定義の厳密な定式化が行われる。特に、公開鍵暗号の安全性は、一方向性、強秘匿性、頑強性などの安全性概念と、選択平文攻撃や選択暗号文攻撃など、攻撃者の攻撃能力/環境の組み合わせにより定式化されることや、”IND-CCA2安全性”が望ましい安全性であることが説明される。また、各種の安全性定義間の相互関係が厳密な証明とともに示されている。

第6章「公開鍵暗号の構成」では、種々の公開鍵暗号方式の構成法が記されている。最初に、代表的なIND-CCA2安全な公開鍵暗号方式であるOAEPとCramer-Shoup暗号の、構成及び安全性証明が示される。その後、暗号化したまま平文の操作を行うことができる準同型暗号、長い平文を効率的に暗号化できるハイブリッド暗号の考え方や具体的な構成法が紹介されている。

第7章「ディジタル署名」では、「データの完全性」を保証する技術であるディジタル署名の安全性定義や構成法が説明される。特に、RSA-FDH署名など、いくつかの重要な方式については、厳密な安全性証明が示されている。また、標準的なディジタル署名には無い機能や性質を持つディジタル署名がいくつか紹介されている。

第8章「IDベース暗号」では、2000年頃から急速に研究が進展した、公開鍵暗号の拡張の一種であるIDベース暗号について、安全性定義、具体的な構成などが説明されている。そして、IDベース暗号の一つの暗号理論上の応用として、IND-CCA2安全な公開鍵暗号を構成する方法であるCanetti-Halevi-Katz変換の安全性証明が与えられている。

◇

他の暗号技術の教科書と一線を画する本書の最も大きな特徴は、(全ての演習問題に解答がついている！ことに加えて、)暗号理論における種々の基礎的な要素技術(一方向性関数、公開鍵暗号、ディジタル署名)などの厳密な安全性定義の定式化や、暗号理論においてマイルストーンとなる種々の暗号方式の安全性証明を、暗号理論の研究分野で国際的に活躍する著者らにより、現代暗号理論で主流の記述スタイルで沢山書かれているのを、日本語で読めることである。駆け出しの暗号理論の研究者は、本書の証明の記述スタイルを手本とすべきである。

学部生・大学院生などの駆け出しの暗号理論の研究者や、暗号技術を取り扱う技術者など、暗号技術についての、単なる概念の説明などを超えた厳密な安全性の定義や証明の内容・手法を理解(、そして論文執筆という形で実践)したい方に、本書を強くお勧めしたい。