暗号理論と楕円曲線

最新の暗号理論がわかる。情報社会を支える暗号技術の最先端「楕円暗号」。その理論を第一線の研究者たちがわかりやすく解説。

楕円曲線を使う公開鍵暗号を中心に、その土台となる数学から、ペアリング、多変数公開鍵暗号、誤り訂正符号に基づく暗号、暗号プロトコルの安全性までを数学の側から解説した理論書です。『暗号理論と楕円曲線』は辻井重男、笠原正雄 編著、有田正剛、境隆一、只木孝太郎、趙晋輝、松尾和人 著で、2008 年 9 月に森北出版から刊行されました。副題は「数学的土壌の上に花開く暗号技術」です。版元の紹介文は、刊行時点で楕円暗号を情報社会を支える暗号技術の最先端と位置づけ、その理論を第一線の研究者たちがわかりやすく解説する本と案内しています。

全 8 章の構成、数学と暗号の交流から安全性まで

章立ては 1 章「数学と暗号-その交流の軌跡」から 8 章「暗号プロトコルの安全性」までの全 8 章です。2 章「暗号の基盤となる数学」で道具をそろえたあと、3 章「楕円曲線上の公開鍵暗号」、4 章「超楕円曲線上の公開鍵暗号」、5 章「ヴェイユペアリングとその暗号への応用」と曲線を使う暗号の章が続き、6 章「多変数公開鍵暗号とグレブナ基底」と 7 章「誤り訂正符号に基づく暗号」で楕円曲線とは別の数学に立つ公開鍵暗号へ広がります。書名は楕円曲線を掲げていますが、扱う範囲はそれより広く、公開鍵暗号を支える数学を幅広く扱う構成です。

楕円曲線とペアリングが暗号で果たす役割

公開鍵暗号は、暗号化 と復号に別々の鍵を使う方式で、片方向には計算しやすく逆向きには極めて難しい数学の問題を安全性の根拠にしています。有限体の上の楕円曲線では、曲線上の点どうしに足し算を定義すると群になり、ある点を何倍かした結果からその倍数を求める問題、いわゆる楕円曲線上の離散対数問題が、知られている一般的な解き方では非常に難しくなります。素因数分解や有限体の離散対数を使う方式に比べて、より短い鍵で同程度の安全性を見込めることが、楕円曲線が実用の暗号に取り入れられてきた理由です。一方、ペアリングは 2 つの点から有限体の元を作る写像で、特定の曲線では離散対数問題を有限体の問題へ移して解きやすくしてしまう攻撃の道具になると同時に、ID をそのまま公開鍵に使う暗号のような新しい仕組みを作る材料にもなります。超楕円曲線は楕円曲線を一般化した曲線で、扱う群の構成が一段複雑になります。

多変数暗号と符号暗号、楕円曲線以外の公開鍵暗号

6 章と 7 章が扱う系統は、楕円曲線や素因数分解とは別の難しさに安全性を置いています。多変数公開鍵暗号は多数の変数を含む連立の多項式方程式を解く難しさを、符号に基づく暗号は誤りを含んだ符号語から元の情報を復元する難しさを根拠にしており、グレブナ基底は連立の多項式方程式を扱う代数の計算手法です。量子計算機の上で動くショアのアルゴリズムは素因数分解と離散対数問題を効率よく解けることが知られていますが、これらの系統にはそうした解き方が知られていません。本書の 3 章から 7 章は、楕円曲線、超楕円曲線、ペアリング、多変数公開鍵暗号、誤り訂正符号に基づく暗号の順です。

数学から暗号を理解したい読者へ、向かない目的

暗号ライブラリの使い方やプログラムの実装例を求める人には目的が合いません。また 2008 年 9 月の刊行なので、その後に進んだ暗号の標準化や新しい方式の動向は含まれていません。

楕円曲線暗号を道具として使うだけでなく、なぜ安全と言えるのか、どこに弱点が生まれうるのかを数学の言葉で確かめたい人にとって、本書は楕円曲線からペアリング、別系統の公開鍵暗号までを 1 冊で扱う理論書です。最後の 8 章は暗号プロトコルの安全性を扱います。