耐量子電子署名HAWKで、格子の対称性を利用して秘密鍵の回復を速める攻撃が見つかった。Anthropicは、AIモデルClaude Mythos Previewと開発した攻撃により、実効的な鍵長が従来評価の半分になるとしている。
標準化候補の署名方式で鍵回復攻撃を改良
Anthropicの研究者は、AIモデルClaude Mythos Previewとともに、耐量子電子署名方式HAWKの鍵回復攻撃を改良した。対象は、量子コンピューターに対する安全性を目指して設計された署名方式である。
HAWKは、米国立標準技術研究所(NIST)が進める追加電子署名方式の選定で、第3ラウンドの候補となっている。その安全性は、格子同型問題という数学的問題を解く難しさに基づく。
格子の未利用の対称性が攻撃の条件を満たす
攻撃の手掛かりになったのは、格子の構造を保つ変換のうち、自明ではないものを指す「非自明な自己同型」だった。先行研究は、この対称性を効率よく見つけられれば攻撃が可能になると示していたが、HAWKの格子で実際に見つけられるかは未解決だった。
Anthropicによると、Claude Mythos PreviewはHAWKの格子に、それまで利用されていなかった非自明な自己同型を見いだした。この対称性の利用によって、候補を列挙して鍵の回復を目指す攻撃が従来より速くなった。
実効的な鍵長は半分、攻撃はなお指数時間
Anthropicは、高速化した攻撃によってHAWKの実効的な鍵長が半分になるとしている。これは、鍵そのものを短く変更したという意味ではなく、攻撃に対する安全性の評価が下がったことを示す。
改良後の攻撃も、計算時間が指数的に増える性質は残る。Anthropicは、この攻撃の下で従来と同じ安全性を得るには、HAWKの鍵サイズを2倍にする必要があるとしている。
人間の助言を受けた半自律探索で約60時間
攻撃の発見に向けて、Claude Mythos Previewは時折人間の助言を受けながら、半自律的に文献調査、数学的推論、計算実験を進めた。Anthropicは、約60時間の作業で最良既知の攻撃を改良し、開発にかかったAPI費用は約10万ドルだったとしている。
Anthropicは6月にHAWKの開発者へ攻撃を共有した。成果の公開と同時に、NISTの公開メーリングリストへ開示する調整も行った。