数学の定理を活用して耐量子暗号標準候補のアルゴリズム解読に成功――Microsoftによる賞金5万ドルの解読チャレンジで

量子コンピューティングへ移行しつつあるデジタル時代といえる現在、クラッキング攻撃からデータを保護することは、私たちの最大の課題の1つだ。

2022年7月に、アメリカ国立標準技術研究所（NIST）は、耐量子暗号標準化プロジェクトの一環で、標準化する4つの暗号化アルゴリズムを選定し、さらに複数の暗号化アルゴリズムを精査して4つのアルゴリズムを追加することを検討していると発表した。後者の候補群の中には、AmazonやMicrosoft Research、欧米の大学などの共同研究による「Supersingular Isogeny Key Encapsulation（SIKE）」が含まれていた。

Microsoftは、2021年6月末に「SIKE Cryptographic Challenge」として世界中の研究者を対象とした課題を公表し、SIKEアルゴリズムを解読して課題を解決できた者には賞金5万ドル（約660万円）を提供するとした。その結果、2022年7月に、パソコン1台で課題を1時間足らずで解決したという報告がなされた。このハッキングには強力なコンピューターが使われたわけではなく、カナダのクイーンズ大学のErnst Kani教授が1997年に確立した数学の定理が用いられていた。

Kani教授の主な研究テーマは、代数幾何の技術を用いて数論の問題を解くという数論幾何学だ。解決しようとしているのは、3世紀頃の数学者であるアレキサンドリアのディオファントスが著書に記したいわゆる「ディオファントス問題」と呼ばれる一連の代数の問題だ。Kani教授によるディオファントス問題についての研究は、ベルギーのルーヴェン・カトリック大学の研究者であるWouter Castryck氏とThomas Decru氏がSIKE解読に成功したことから再注目されるようになった。

SIKEは、超特異同種写像ディフィー・ヘルマン（Supersingular Isogeny Diffie-Hellman：SIDH）鍵交換プロトコルをベースとした耐量子鍵カプセル化メカニズムであり、Catryck氏とDecru氏は、1997年にKani教授が確立した「接着と分裂（glue and split）」定理に基づいて、SIDHに対する鍵復元攻撃を研究していた。

ドーナツのような形をしていて真ん中に穴が開いている物体が、種数1の曲面（genus one curve）として知られる楕円曲線の視覚モデルだ。Kani教授とドイツの数学者Gerhard Frey氏は、種数1の曲面2つを組み合わせて新しい物体、すなわち、種数2の曲面（genus two curve）を作ろうと考えた。これは、2つのドーナツを並べて強固にくっつけたようなものとイメージすることができる。彼らは、この構築された種数2の曲面の特性を利用して、「接着」された元の種数1の曲面の特性を推論しようとした。

Kani教授は、楕円曲線の任意のペアを接着することで、元の構築を一般化した。しかし、この場合、時々失敗することがあり、2つのドーナツが単一の点でしか接触しないような物体を構築することがある。1997年に発表された論文では、構築が失敗、あるいは、「分裂」する場合の正確な条件を分析している。Castryck氏とDecru氏は、この失敗時の特徴をSIKEに対する攻撃手法に利用した。

Kani教授は、純粋数学を研究すること自体が目的であるため、暗号化アルゴリズムなど実世界への応用は考えていないという。「しかし、後に、そのような研究の多くは異なる目的にとって役立っている。何百年も前にフェルマーが定理を提案したとき、彼が意図したのはいくつかの大きな数を因数に分解できるようにすることだった。暗号技術に応用されたのは、ずっと後の1978年のことだ。基本的に、今日、私たちがデータ暗号化に使っているすべての方法は数学に基づいている」とKani教授は述べている。

数学の定理を活用して耐量子暗号標準候補のアルゴリズム解読に成功――Microsoftによる賞金5万ドルの解読チャレンジで