Full-Key Recovery and Forgery from One MQOM v2.1 Signature

想像してみてください。あなたは友人に秘密のメッセージを送ろうとしていますが、そこはいつか超高速のコンピュータ（量子コンピュータと呼ばれます）が存在するかもしれない世界です。これらの未来の機械は、今日私たちが秘密を守るために使っているほとんどの鍵を破ってしまう可能性があります。これに備えて、科学者たちは「ポスト量子署名」と呼ばれる、より強力な新しいデジタルロックを構築しています。これは、手紙に押す特別な種類の蝋封（ろうふう）のようなものだと考えてください。たとえ泥棒が普通の鍵を粉砕できる魔法のハンマーを持っていたとしても、この新しい蝋封は、耐え抜くはずの素材で作られています。

この中で、最も有望な新しいロックの一つとして、MQOMと呼ばれるものがテストされています。これは、巨大で複雑なパズルのような仕組みです。署名をする際、送り手は「目撃者（ウィットネス）」（隠された鍵）を使用して、多くの変数を含む数学の問題を解きます。しかし、秘密そのものを見せることなく、その問題を解いたことを証明するために、「MPC-in-the-head」という巧妙なトリックを使います。これは、送り手が、秘密の断片をそれぞれ持っている一つのチーム全体であるかのように振る舞う様子を想像してください。彼らは、チームが協力してパズルを解いたことを証明するために十分な情報を公開しますが、実際の秘密の断片を明かすには至らないようにゲームを進めます。もし数学的な整合性が取れていれば、その署名は有効となります。私たちがこれを重視するのは、もしこれらの新しいロックに隠れた亀裂があれば、未来のデジタル上の安全性が、その時が来る前に崩れ去ってしまう可能性があるからです。

では、この論文のストーリーについてお話ししましょう。研究者のホセ・ルイス・デルガド（José Luis Delgado）氏は、このMQOMロックの特定のバージョン（バージョン2.1）を詳しく調査し、それを破る驚くほど単純な方法を発見しました。この論文は、もし攻撃者がシステムからたった一つの有効な署名を入手できれば、署名全体の秘密鍵を特定し、あらゆるメッセージに対して新しい署名を偽造できると主張しています。それは、もし泥棒があなたが一度玄関のドアを開けるのを目撃しただけで、その一度の覗き見によって、あなたの家のあらゆる鍵を開けるマスターキーを作れてしまうようなものです。

この「魔法のトリック」がどのように機能するかを、物語を通して説明します。秘密鍵は、長い隠された宝の地図だと想像してください。MQOMシステムは、この地図を枝を持つ巨大な木の中に隠しています。署名を行うとき、システムはあなたに、木を登っていく特定の経路（隠された葉への道）を示しますが、その葉自体は覆い隠したままにします。しかし、同時に「兄弟経路（シブリング・パス）」、つまり隠された葉の隣にある枝のリストも提供します。この木の構造上、もしあなたが隠された葉の隣にある枝を知っていれば、秘密の地図の小さな接頭辞（プレフィックス）を知っている場合に、その隠された葉がどのようなものになるかを正確に導き出すことができます。

論文によると、システムは「コミットメント」、つまり隠された葉が入った封印された封筒のようなものも残しています。研究者は、この兄弟経路（枝）と封印された封筒を組み合わせることで、一つの巨大な方程式を書くことができると気づきました。この方程式には、秘密の地図の小さな接頭辞という一つの未知数が含まれています。攻撃者は地図全体を推測する必要はありません。ただ、この一つの方程式を解いて、その小さな接頭辞を見つけ出せばよいのです。

この接頭辞を見つけたら、すでに持っている署名は「補正接尾辞（コレクション・サフィックス）」、つまり「あなたが今見つけた接頭辞に合わせるための、地図の残りの部分はこちらです」という短いメモのようなものを提供してくれます。この接頭辞とメモを組み合わせることで、攻撃者は完全な秘密の地図（フル署名鍵）を再構築できるのです。この鍵さえあれば、攻撃者はあらゆる新しいメッセージに署名することができ、システムはその署名を本物として受理します。

この論文は単にこれが可能だと推測しているわけではありません。彼らは実際に数学的な計算とコンピュータによる検証を行い、これを証明しました。彼らは、異なるセキュリティ強度レベル（カテゴリーI、III、Vと呼ばれます）に対して、この方程式を解くためにどれだけの計算能力が必要かを正確に算出しました。その結果、すべてのカテゴリーにおいて、必要な計算量は、このロックが安全であるとされるセキュリティ限界よりも低いことが分かりました。

最も簡単なレベル（カテゴリーI）では、攻撃には約 $2^{142.335112}$ 回の操作が必要です。中程度のレベル（カテゴリーIII）では、地図をスキャンする方法によって異なりますが、約 $2^{206.774558}$ または $2^{206.988685}$ 回の操作が必要です。最も難しいレベル（カテゴリーV）では、約 $2^{271.794162}$ 回の操作を要します。あらゆるケースにおいて、攻撃者が踏むべきステップの数は、ロックが耐えられるように設計されていたステップの数よりも少なくなっています。

研究者たちは数学的な検証にとどまりませんでした。彼らは実際に攻撃を実行するコンピュータプログラムを構築しました。彼らは本物の署名を取り込み、方程式を解き、秘密鍵をバイト単位で正確に復元し、その後、その鍵を使って全く新しいメッセージに署名を行いました。システムの検証器（ベリファイア）は、その新しい署名をチェックし、「はい、これは有効です」と判定しました。これにより、この攻撃が理論上の話ではなく、現実の世界でも機能することが証明されました。

また、論文ではいくつかの設定を変更することで問題が解決するかどうかについても検討しました。彼らは、プロセスに「ソルト（乱数）」を加えることは、方程式の中の数字を変化させるものの、攻撃を阻止することにはならないと結論付けました。方程式自体は依然として存在しており、見た目が少し変わるだけなのです。これを真に修正するためには、設計者は、木の経路と秘密の関係、あるいは葉のコミットメントのされ方、または補正メモの生成方法を根本的に変更する必要があります。

要約すると、この論文は、現在のバージョンのMQOMロックには、そのまま通り抜けられてしまうほど大きな穴が開いていることを示しています。たった一つの署名をマスターキーに変えてしまい、攻撃者が設計された耐性を下回る労力でメッセージを偽造することを可能にしています。著者は、他の人々が自らの成果を確認できるようにコードと結果を共有しており、MQOMの設計者たちが、このシステムを将来的に安全であるとみなす前に、これらの特定の箇所を修正（パッチを適用）する必要があると提言しています。