量子コンピュータによる既存システムの破綻

インターネットおよびその他の通信システムの機能は、安全で効率的な暗號化アルゴリズムに依存しています。このようなアルゴリズムにより、インターネットエンティティは秘密に通信することができ、また通信相手の身元を確認することもできます。Advanced Encryption Standard（AES）などの対稱鍵アルゴリズムは、通信者間で共有鍵を使用することで機密性を実現しています。公開鍵暗號方式には、共有鍵を導出するための鍵合意アルゴリズム（例：Diffie-Hellman）と、各エンティティの身元を認証するための検証アルゴリズム（例：RSAアルゴリズム）があります。

RSAとDiffie-Hellmanのセキュリティは、大數の因數分解や離散ログの発見などの計算問題に基づいています。このような計算問題は、従來のコンピュータと古典的なアルゴリズムを使用して解決するには、指數関數的に困難になります。ムーアの法則を考慮しても、因數分解アルゴリズムに非常に大きな進歩がない限り、RSA、Diffie-Hellmanなどのアルゴリズムは長期にわたって安全であると考えられていました。

1994年に発明されたShorのアルゴリズムによって、この狀況は変わりました。これは、大數を因數分解するためのアルゴリズムですが、このアルゴリズムの重要な部分は、量子コンピュータでしか実行できません。Shorのアルゴリズムを実行するのに十分な規模を持つ量子コンピュータを実際に構築できれば、大數を非常に効率的に因數分解でき、RSAと関連するアルゴリズム（Diffie-Hellmanなど）のセキュリティは崩壊してしまいます。インターネットへの影響は甚大です。特定の問題を解決できれば、2048ビットのRSAを破るために2000萬個の量子ビット（キュービット）を備えた量子マシンを構築できると推定されています^[1]。現在の実験的な量子コンピュータは、50キュービット程度を備えています。

量子コンピュータの拡張性に関しては不確実であるため、このような実用的な量子コンピュータをいつ構築できるか、あるいは実現可能かどうかは不明です。開発の進展を測る1つのマイルストーンとしては、量子優位性の概念が挙げられます。これにより、量子コンピュータは、従來のコンピュータでは手の屆かなかったタスクを実際に解くことができます。何十億ドルもの研究資金が投入されている中で、産業界は今後數年以內に量子優位性を達成できると予測しています^[2]。これは公開鍵アルゴリズムがすぐに破られる危険があることを意味するわけではありませんが、産業界はShorや他の量子アルゴリズムに影響されない、耐量子アルゴリズムへの移行の準備を始める必要があることを意味します。

量子コンピュータの能力を持ってしても、対稱鍵アルゴリズムは安全であることを當社は指摘しています。量子コンピューティングでは対稱鍵の有効長が半減する可能性があると推定されているため、AES-256のようなアルゴリズムは置き換える必要なく安全です。

強化されたセキュリティを提供する耐量子アルゴリズムの導入

ファーウェイは、製品の長期的なセキュリティを確保するために、耐量子アルゴリズムを早期に製品に導入する予定です。最も重要な點は、鍵合意のための安全な耐量子アルゴリズムを導入することです。これは、量子コンピュータが実用化されると、鍵合意メッセージを格納し、遡及的に攻撃できるためです。従來の鍵合意アルゴリズムを使用し続けた場合、量子コンピュータの実用化以前に行われたセッションは前方秘匿性（forward security）を維持できない可能性があります。

ファーウェイはポスト量子アルゴリズムのさまざまな標準化活動を興味深く見守っています。よく知られている標準化作業の1つでは、世界中の學界の協力を得て、數十ものポスト量子アルゴリズムの分析を進めています。この標準化作業は2024年までに終了する予定ですが、最終ポートフォリオを構成することになるアルゴリズムの性質と數は予測が困難です。

鍵合意のホーディング問題を防止するために、2024年までの期限に先立って、このようなアルゴリズムの一部を製品に導入する予定です。これには、6つのカテゴリに分類できる候補アルゴリズムの特性を考慮する必要があります。各カテゴリは、アルゴリズムが持つセキュリティの実裝特性と成熟度の両方に特別な意味を持ちます。そのようなカテゴリは以下のとおりです。

• ハッシュベースのアルゴリズム。このクラスのアルゴリズムは、署名にのみ使用できます。制限の1つは、インスタンス化のそれぞれが限られた數の署名の生成にのみ使用できることです。この利用を最適化する方法の研究が続いています。ただし、ハッシュベースのアルゴリズムのセキュリティは十分に理解されています。
• Oil and Vinegar方式のような多変數アルゴリズム。このクラスのアルゴリズムは、署名にのみ使用できます。このクラスのアルゴリズムは非常に小さなサイズの署名を生成しますが、多くの多変數アルゴリズムのセキュリティは十分には理解されていません。
• 1996年に発明された格子ベースのアルゴリズム（NTRU署名方式など）。格子は、署名と鍵交換アルゴリズムの両方で使用できます。通常の格子の場合、その特性は最適ではありませんが、リングに基づく格子のような數學的構造を導入すると、鍵のサイズが小さくなり、セキュリティに影響する可能性があります。
• 超特異同種（Super-singular isogeny）ベースのアルゴリズムは、楕円曲線上のウォークに基づく鍵交換アルゴリズムを提供します。これは、比較的低速でコンパクトな鍵のサイズを特徴とするポスト量子アルゴリズムのカテゴリです。
• ? McEliece暗號化アルゴリズムに代表されるように、符號ベースのアルゴリズムはセキュリティに関しては保守的です。適切に選択されたパラメーターにより、このアルゴリズムのセキュリティは1978年の発明以來、劣化していません。非常に大きな公開鍵のような不利なパラメーターの場合には弱點がありますが、長期鍵の変更がほとんどないアプリケーションでの鍵交換に適しています。その他のタイプの符號ベースのアルゴリズム（低密度のパリティチェック符號に基づくアルゴリズムなど）は、高度なセキュリティを提供しながら、公開鍵のサイズを大幅に低減することができます。
• ゼロ知識証明や軽量ブロック暗號要素に基づくRainbow署名アルゴリズムなどのその他のアルゴリズム。

古いシステムから新しいシステムへの移行

ファーウェイのような企業は、鍵交換メッセージの前方秘匿性の問題にどう対処するかについて、いくつかの選択肢を持っています。Diffie-Hellmanに代わる有望なポスト量子アルゴリズムをすぐに実裝できますが、學界が新しい耐量子アルゴリズムの領域を精査する際に、このアルゴリズムが今後數年間のうちに破られるかもしれないというリスクをもたらします。または、會社の判斷として、標準化活動が終了するまでの數年間、いかなる行動も延期することを選択する可能性もあります。その場合、鍵交換メッセージの前方秘匿性の問題はその間は未解決のままとなります。

第3の選択肢は、Diffie-Hellmanと耐量子鍵交換メカニズムの候補の両方を可能にするハイブリッド方式を実裝することです。この選択肢は、実用的な量子コンピュータが最終的に登場しても、耐量子メカニズムを直接破ることができないため、リスクを大幅に軽減します。他方、耐量子メカニズムの問題がその間に見つかった場合、Diffie-Hellmanアルゴリズムによってある程度の中期的な保護が提供されます。

理想的には、耐量子アルゴリズムやハイブリッド鍵交換アルゴリズムは、TLSやIPsecなどの既知のプロトコルと直接融合する必要があります。実際には、実裝の難易度とパラメーターの特性（大きな鍵、または帯域幅の消費など）の両方の點で、耐量子アルゴリズムはレガシーアルゴリズムと比較して複雑です。プロトコルの慎重な研究とアルゴリズムの最適化により、ハイブリッド鍵交換方式を使用した場合のパフォーマンスへの影響が軽減されます。