今日の暗号化プロトコルが失敗した場合、機密メッセージの送信、安全な金融取引、またはデータの認証など、オンライン接続を保護することは不可能になります。 誰でも何にでもアクセスできました。 誰もが誰かのふりをすることができます。 デジタル経済は崩壊するでしょう。
いつ（または if）完全に機能する量子コンピューターが利用可能になると、まさにそれが起こり得る. その結果、2017 年に米国政府の国立標準技術研究所 (NIST) は、「ポスト量子」暗号を実現するための最良の方法を見つけるための国際競争を開始しました。
先月、政府機関は最初の勝者グループを選択しました.XNUMXつのプロトコルは、いくつかの修正を加えて、量子シールドとして展開されます. また、まだ検討中のXNUMX人の追加候補も発表しました。
その後、30 月 XNUMX 日、XNUMX 人の研究者が、 それらの候補のXNUMXつを破った ラップトップで XNUMX 時間。 (それ以来、他の人は攻撃をさらに高速化し、数分でプロトコルを破りました.) スティーブン・ガルブレイス、ニュージーランドのオークランド大学の数学者およびコンピューター科学者。 攻撃の根底にある数学が驚くべきものであっただけでなく、ポスト量子暗号の (大いに必要とされていた) 多様性を減少させました。
「それはちょっと残念だ」と彼は言った クリストファー・パイケルト、ミシガン大学の暗号学者。
この結果は、ポスト量子暗号コミュニティを揺るがし、勇気づけました。 この攻撃 (および前のラウンドからの別の攻撃) が突然、デジタル鋼のドアのように見えるものを濡れた新聞紙に変えたため、震えました。 「それは突然やってきた」と彼は言った ダスティン・ムーディ、NIST標準化の取り組みをリードする数学者のXNUMX人。 しかし、暗号化方式が破られる場合は、実際に使用される前に破られるのが最善です。 「あなたを通り抜ける多くの感情があります」と言いました デビッド・ジャオ、カナダのウォータールー大学の数学者であり、IBMの研究者とともに ルカ・デ・フェオ、2011年に議定書を提案しました。確かに驚きと失望がその中にあります。 「でも」とジャオは付け加えた。「少なくとも今は壊れてしまった」
曲線の間の秘密の散歩
Jao と De Feo は、よく知られているプロトコルと似ていると同時に適切に異なる暗号システムの可能性を見出していました。 彼らのスキームは、超特異アイソジェニ Diffie-Hellman プロトコル (SIDH) と呼ばれ、楕円曲線を処理します。これは、今日展開されている最も普及しているタイプの暗号の XNUMX つで使用されているものと同じ数学オブジェクトです。 しかし、それはまったく異なる方法でそれらを使用しました。 これは、NIST が検討していた最もコンパクトなスキームでもありました (他の多くの候補よりも遅いというトレードオフがあります)。
そして、「数学的には、非常にエレガントです」と Jao 氏は述べています。 「当時、それは素晴らしいアイデアのように思えました。」
Alice と Bob の XNUMX 者が、潜在的な攻撃者の注意深い視線の下でも、秘密裏にメッセージを交換したいとします。 それらは、グラフと呼ばれるエッジによって接続されたポイントのコレクションから始まります。 各点は異なる楕円曲線を表します。 特定の方法で (アイソジェニーと呼ばれるマップを介して) ある曲線を別の曲線に変換できる場合は、点のペアの間にエッジを描画します。 結果として得られるグラフは巨大で、簡単に迷子になります。グラフの端に沿って比較的短い距離を歩くと、完全にランダムに見える場所に行き着きます。
Alice のグラフと Bob のグラフはすべて同じ点を持ちますが、エッジは異なります。異なるアイソジェニによって定義されています。 Alice と Bob は同じポイントから開始し、それぞれのグラフのランダムなエッジに沿ってホップしながら、あるポイントから別のポイントへのパスを追跡します。 次に、それぞれが終了場所を公開しますが、パスは秘密にします.
アリスはボブの最終ポイントに行き、ボブはアリスの最終ポイントに行きます。 それぞれが秘密の散歩を繰り返します。 彼らは、両方が同じポイントに到達するようにこれを行います。
この場所は秘密裏に発見されているため、アリスとボブはそれを秘密鍵として使用できます。これにより、互いのメッセージを安全に暗号化および復号化できるようになります。 攻撃者は、アリスとボブがお互いに送信する中間点を見ても、アリスまたはボブのシークレット ウォークがわからないため、その最終エンドポイントを特定することはできません。
しかし、SIDH を機能させるには、Alice と Bob が散歩に関する追加情報を交換する必要もあります。 その余分な情報が、SIDH の没落につながったのです。
古い数学の新しいひねり
トーマス・デクル SIDH を打破するつもりはありませんでした。 彼はそれを発展させようとしていた — 別のタイプの暗号化を強化する方法を一般化する. それはうまくいきませんでしたが、アイデアがひらめきました。彼のアプローチは SIDH の攻撃に役立つかもしれません。 そして彼は近づいた ウーター・カストリック、ベルギーのルーヴェン・カトリック大学の彼の同僚であり、彼の元博士号顧問の XNUMX 人である XNUMX 人は、関連する文献に飛び込みました。
彼らはその数学者によって出版された論文を偶然見つけた. エルンスト・カニ それは、「SIDH にほぼ即座に適用できる」定理であったと Castryck 氏は述べています。 「私たちが気づいたら…攻撃は1997日かXNUMX日で非常に迅速に行われたと思います。」
最終的に、アリスのシークレット ウォーク (したがって共有鍵) を復元するために、Catryck と Decru は XNUMX つの楕円曲線 (アリスの開始曲線とアリスがボブに公開して送った曲線) の積を調べました。 この組み合わせは、アーベル曲面と呼ばれる一種の曲面を生成します。 次に、これらのアーベル曲面、カニの定理 (アーベル曲面を楕円曲線に関連付ける)、およびアリスがボブに与えた追加情報を使用して、アリスが行った各ステップを明らかにしました。
「これは、[特定のアーベル面] にロックインできるホーミング信号のようなものです」とジャオ氏は言います。 「そして、その信号は、これが正しい [秘密の散歩] を見つけるために次のステップに進むべき道であることを示しています。」 これにより、アリスとボブの共有鍵に直接たどり着きました。
「これは非常に予想外のアプローチであり、より複雑なオブジェクトを使用して、より単純なオブジェクトに関する結果を導き出します」と Jao 氏は述べています。
「この技術が使われているのを見て、とても興奮しました」と彼は言いました。 クリスティン・ラウターMeta AI Research の数学者兼暗号学者であり、アイソジェニー ベースの暗号の開発を支援しただけでなく、アーベル サーフェスにも取り組んできました。 「それを破る方法として考えなかったのは恥ずべきことです。」
Castryck と Decru の攻撃は、SIDH プロトコルの最低セキュリティ バージョンを 62 分で破り、最高セキュリティ レベルをわずか 10 日足らずで破りました。 その直後、別の専門家が攻撃を微調整したため、セキュリティの低いバージョンを破るのにわずか XNUMX 分、セキュリティの高いバージョンを破るのに数時間しかかかりませんでした。 より一般的な攻撃 過去数週間に投稿された SIDH が救済される可能性は低くなります。
「それは特別な気持ちでした」とカストリックは言いましたが、ほろ苦いものでした. 「お気に入りのシステムの XNUMX つを殺しました。」
流域の瞬間
システムが無条件に安全であることを保証することは不可能です。 代わりに、暗号学者は、十分な時間の経過と、問題を解決しようとする十分な人数に依存して、自信を持っています。 「それは、明日起きて、誰かがそれを行うための新しいアルゴリズムを見つけたことに気付かないという意味ではありません。」 ジェフリー・ホフスタイン、ブラウン大学の数学者。
したがって、NIST のような競争が非常に重要な理由です。 NIST コンテストの前のラウンドで、IBM の暗号学者である Ward Beullens は、次のような攻撃を考案しました。 レインボーと呼ばれる計画を破った 週末に。 Castryck と Decru のように、彼は根本的な数学的問題を別の角度から見た後にのみ攻撃を仕掛けることができました。 SIDH への攻撃と同様に、この攻撃は、提案されているほとんどのポスト量子プロトコルとは異なる数学に依存するシステムを破壊しました。
「最近の攻撃は分水嶺の瞬間でした。 トーマス・パースト、スタートアップ PQShield の暗号学者。 それらは、ポスト量子暗号がいかに難しいか、そしてさまざまなシステムのセキュリティを研究するためにどれだけの分析が必要になるかを強調しています。 「数学的オブジェクトは、ある視点では明らかな構造を持たないかもしれませんが、別の視点では利用可能な構造を持つかもしれません」と彼は言いました. 「難しいのは、適切な新しい視点を特定することです。」
