耐量子計算機暗号

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

インターネットおよびその他の通信システムの機能は、安全で効率的な暗号化アルゴリズムに依存しています。このようなアルゴリズムにより、インターネットエンティティは秘密に通信することができ、また通信相手の身元を確認することもできます。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などの既知のプロトコルと直接融合する必要があります。実際には、実装の難易度とパラメーターの特性（大きな鍵、または帯域幅の消費など）の両方の点で、耐量子アルゴリズムはレガシーアルゴリズムと比較して複雑です。プロトコルの慎重な研究とアルゴリズムの最適化により、ハイブリッド鍵交換方式を使用した場合のパフォーマンスへの影響が軽減されます。