Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

インターネットを、誰もが秘密のメッセージを送ろうとしている、巨大で賑やかな都市だと想像してみてください。メッセージを詮索から守るために、私たちは「暗号化」と呼ばれるデジタルな鍵を使用します。長い間、科学者たちは、鍵なしでは解くのが非常に困難だが、作成するのは極めて容易な複雑な数学パズルを用いて、これらの鍵を作り上げてきました。最近、数字の格子（グリッド）と「ランク」（これは、実際に格子の中にどれだけの情報が詰め込まれているかを測るための、少し凝った言い方です）を用いた、特別な種類の数学を用いた新しいタイプの鍵が提案されました。この新しい鍵の考案者たちは、この設計に「ノイズ」（ラジオの静電気のようなもの）を加えることで、鍵の真の形を隠し、侵入者にはランダムな混乱状態のように見えるようにしたと考えていました。彼らは、この設計は非常に安全であり、超高速の量子コンピュータでさえも破ることができないと主張し、将来の安全な通信に最適な、非常に小さく効率的なものになると約束しました。

しかし、特定の巧妙な手口に依存する手品師のトリックのように、この新しい鍵には隠れた欠陥がありました。タイ・フン・レ（Thai Hung Le）という研究者が、この「ノイズ」は、誰もが考えていたほど秘密の形を隠せていなかったことを発見しました。研究者は、巧みな推測と代数的な探偵工作を組み合わせることで、静電気の層を剥ぎ取り、その下にある元の隠された構造を明らかにする方法を見つけ出したのです。それは、まるでトランプの家（カードタワー）が秘密の設計図を持っており、それが霧に覆われていたとしても、霧を適切な角度から眺めれば、設計図がかすかに見える状態であったようなものです。この発見は重大な意味を持ちます。なぜなら、この新しい鍵は宣伝されているほど安全ではないことを意味しており、設計者たちは、私たちのデータを保護するために使い始める前に、設計図を再考する必要があるからです。

この論文の大きな発見

この論文において、タイ・フン・レは「拡張ガブリードリン行列符号（Enhanced Gabidulin Matrix Code: EGMC）」暗号スキームを打破する新しい方法を提示しています。これらのスキームは、将来の量子コンピュータによる攻撃を生き延びることができる、非常に小さく効率的な暗号鍵を作成する方法として、最近導入されました。これらのスキームの安全性は、特別な構造を持つ数字の格子を取り、そこにランダムな行と列を加える（「ノイズ」を加える）ことで、実際のコードと完全にランダムな混乱との違いを判別することが不可能になるという考えに基づいています。

著者は、この仮定が間違っていることを示しています。ノイズを取り除くあらゆる方法を総当たりで試す（これには膨大な時間がかかるでしょう）代わりに、論文は「ハイブリッド」攻撃を導入しています。これは、巨大でバラバラになったモザイクの中から特定のパターンを見つけ出そうとしている状況を想像してみてください。従来の方法は、すべてのタイルの位置を推測することでした。この新しい方法はよりスマートです。タイルの一行分だけの位置を推測し、それから数学を用いて、残りのタイルがどこにあるべきかを即座に導き出すのです。

論文では、主に2つの方法を詳述しています：

1. 列を推測する： 攻撃者は格子の列がどのようにシャッフルされたかを推測し、その後、行がどのようにシャッフルされたかを代数を用いて解きます。
2. 行を推測する： 攻撃者は行がどのようにシャッフルされたかを推測し、その後、列を解きます。

攻撃者がシャッフルの仕方を解明すれば、ランダムなノイズを取り除き、元の隠された構造を明らかにすることができます。論文では、この構造が「ガブリードリン符号（Gabidulin code）」であることを証明していますが、これは、秘密のパターンさえ分かれば非常に解きやすい数学パズルの一種です。

この論文が実際に破壊するもの

著者は単に小さな亀裂を見つけたのではありません。彼らは窓全体を粉砕したのです。論文は、この攻撃がEGMC暗号スキームに対して提案された全16種類のパラメータセットに対して機能することを実証しています。これは、提案されたすべてのバージョンの鍵が、現在、壊れていると見なされることを意味します。

この攻撃の有効性を実感してもらうために、論文では128ビットのセキュリティ（標準的な安全レベル）を提供するとされていた特定の数値セットについて見ています。著者は、この攻撃によって、このセキュリティレベルがわずか35ビットにまで低下することを示しています。暗号の世界において、これは、百万桁の組み合わせを持つ金庫から、子供でも数秒で開けられるような錠前へと格下げされるようなものです。

論文は、この力の具体的な例を提供しています。研究者たちは、彼らの手法を用いることで、その128ビットのセキュリティレベルの秘密鍵を10分未満で回収することができました。これは単なる理論的なアイデアではありませんでした。彼らは実際に、これを行うためのコンピュータプログラムを構築したのです。

この論文が否定していること

この論文が「うまくいかない」と言っていることに注意することが重要です。著者は、これらのコードを破ろうとする以前の試みは、「組合せ論的（combinatorial）」な手法、つまり行と列の両方のシャッフルを同時に推測することに依存していたと説明しています。論文は、この従来の方法は、彼らの新しい「ハイブリッド」アプローチと比較して、あまりにも遅く非効率であると主張しています。

さらに、論文は、単にパラメータを大きくすること（より多くのノイズを加えること）が、すべてのケースにおいて問題を解決するかどうかについても議論しています。著者は、これらのコードの特定のタイプ、具体的にはノイズの要因の一つ（追加の行または追加の列のいずれか）がゼロである場合、攻撃があまりにも速くなり、「多項式時間（polynomial time）」で実行されることを示しています。これは、特定のケースにおいては、鍵のサイズをどれほど大きくしても、攻撃は依然として十分に高速であることを意味します。この問題を潜在的に解決する唯一の方法は、両方のノイズ要因がゼロではなく、攻撃を阻止できるほど十分に大きくなるように、根本的な設計を変更することであると論文は示唆していますが、著者は、そうすることで鍵やメッセージが使い物にならないほど大きくなってしまう可能性があると警告しています。

彼らの確信度はどの程度か

論文は、その結果に非常に自信を持っています。著者は単に推測したのではなく、自身の攻撃がどのように機能するかについての完全な数学的証明を提供し、それを動作するコンピュータ実装によって裏付けました。彼らは、この攻撃が提案されたスキームのすべてのバージョンを破壊することを明示的に述べています。また、彼らの手法を以前の攻撃と比較し、その方法が大幅に高速で強力であることを示しています。論文は、EGMC暗号スキームはもはや使用するには安全ではなく、セキュリティコミュニティは別の設計に移行する必要があると結論付けています。