シノプシス
Ansys

シノプシスのPUF:ポスト量子暗号時代への備え

暗号技術に対する量子コンピューティングの脅威について、最近耳にすることが増えているのではないでしょうか。それに伴い、この「量子脅威」とは何か、そしてそれが暗号化ソリューションにどのような影響を与えるのかについて、多くの疑問を持たれていることでしょう。量子コンピューティングとそれが暗号技術に与える影響について、よくあるいくつかの疑問を見ていきましょう。

量子コンピュータとは

量子コンピュータは、非常に高速な汎用スーパーコンピュータでもなければ、魔法のように大規模な並列処理を行うものでもありません。そうではなく、独自の量子アルゴリズムを効率的に実行します。これらのアルゴリズムは、理論上、特定の非常に特殊な計算を、いかなる従来のコンピュータよりもはるかに効率的に実行できます。

しかし、実用的な量子コンピュータ、すなわち現代の従来のコンピュータの性能を実際に凌駕できるコンピュータの開発は、極めて困難です。量子コンピューティング技術は1980年代から開発が進められており、2010年代以降、動作する量子コンピュータは徐々に向上しています。しかし、現在の最先端技術を将来に外挿し、従来のコンピュータにおけるムーアの法則と同等の指数関数的な向上の仮定を置いたとしても、実用的な量子コンピュータが現実のものとなるには、依然として少なくとも15〜20年はかかると専門家は予測しています(1)、(2)。

暗号技術に対する量子脅威とは

1990年代に、一部の量子アルゴリズムが特定の従来の暗号技術のセキュリティに影響を与える可能性があることが発見されました。懸念されている量子アルゴリズムには、次の2つがあります。

  1. ショアのアルゴリズムは、1994年にピーター・ショア(Peter Shor)によって考案されたもので、大きな整数を素因数分解し、いくつかの関連する数論的問題を解くための効率的な量子アルゴリズムです。現在、従来のコンピュータにおいて効率的な素因数分解アルゴリズムは知られておらず、これがいくつかの古典的な公開鍵暗号技術のセキュリティの基礎となっています。
  2. グローバーのアルゴリズムは、1996年にロブ・グローバー(Lov Grover)によって考案されたもので、従来のコンピュータよりも二次関数的に高速に汎用関数の逆関数を探索できる量子アルゴリズムです。暗号技術の観点では、逆関数の探索は総当たり攻撃(未知の秘密鍵の値に対する攻撃など)と同等です。このような攻撃の困難性が、ほとんどの共通鍵暗号プリミティブのセキュリティの基礎を形成しています。

これらの量子アルゴリズムが実用的な量子コンピュータ上で実行可能となった場合、現在の暗号技術のセキュリティに影響を及ぼします。

公開鍵暗号ソリューションへの影響

現在、最も重要かつ広く使用されている公開鍵プリミティブは、RSA、離散対数、または楕円曲線暗号に基づいています。実用的な量子コンピュータが稼働するようになると、これらはすべてショアのアルゴリズムによって効率的に解読されることになります。これにより、現在使用されている事実上のすべての公開鍵暗号が安全ではなくなります。

影響を受ける公開鍵暗号および鍵共有プリミティブにとって、この脅威はすでに現実のものとなっています。現在(または過去に)送受信された暗号化メッセージを傍受して保存する攻撃者は、将来、実用的な量子コンピュータが稼働した際にそれらを復号できるようになります。そのため、現在までに通信された機密性の高い秘密や長期的な機密情報は、すでにリスクにさらされています。

15年未満の短期的な効力を対象として、影響を受ける署名プリミティブを使用する場合、問題の緊急性は低くなります。しかし、実用的な量子コンピュータが利用可能になった時点から、いかなる署名の価値も失効します。したがって、15〜20年以上経過した後でも検証が必要となるような長期的な効力を伴う署名には、影響を受けるプリミティブを使用すべきではありません。

過去10年間にわたり、暗号コミュニティは、ショアのアルゴリズム(または量子コンピュータをはじめとする既知の効率的なアルゴリズム)では解くことができない数学的問題に基づく新しい公開鍵プリミティブを設計してきました。これらのアルゴリズムは一般にポスト量子暗号と呼ばれています。NIST(米国国立標準技術研究所)は最近、標準化に向けたこれらのアルゴリズムの選定を発表しました(3)。

共通鍵暗号ソリューションへの影響

適切に設計された共通鍵プリミティブのセキュリティレベルは、秘密鍵の総当たりに必要な労力と同等です。従来のコンピュータでは、秘密鍵を総当たりするための労力は鍵の長さに直接的に指数関数比例します。実用的な量子コンピュータを使用する場合、グローバーのアルゴリズムにより総当たり攻撃を二次関数的に高速化できます。ただし、必要な労力は依然として指数関数的ですが、鍵の長さの半分にとどまります。したがって、グローバーのアルゴリズムは、任意の長さのアルゴリズムのセキュリティを50%低下させると言えます。

しかし、留意すべき重要な点がいくつかあります。

  • グローバーのアルゴリズムは最適な総当たり戦略(量子コンピュータか否かを問わず)(4)であるため、二次関数的な高速化は最悪ケースのセキュリティ影響となります。
  • グローバーのアルゴリズムの実行を意味のある形で並列化することは不可能であるという強い兆候があります(2)、(5)、(6)、(7)。従来の総当たり攻撃では、使用するコンピュータの数を倍増させれば計算時間は半分になります。量子コンピュータ上のグローバーのアルゴリズムではこのようなスケーリングが不可能であるため、総当たり攻撃におけるその利用は現実的ではありません。
  • グローバーのアルゴリズムを使用して128ビット鍵に対する現実世界の総当たり攻撃を実行する前に、量子コンピュータの性能を飛躍的に向上させる必要があります。現代の従来のスーパーコンピュータでは、128/2=64ビットの指数関数の複雑性を持つ計算を実行可能な時間内(数か月)に完了させることすら困難です。現在の状態と進歩のペースに基づくと、量子コンピュータがそのレベルに到達するには20年以上かかると考えられます(6)。

量子コンピュータが共通鍵暗号に与える実質的な影響は、現時点では非常に限定的です。最悪の場合、現在使用されているプリミティブのセキュリティ強度は(鍵長の)50%に低下しますが、グローバーのアルゴリズムの制約により、それは近い将来においては過度に悲観的な仮定となります。量子による総当たり攻撃に耐えるために共通鍵の長さを倍増させることは、確実に問題を解決する非常に広範な包括的対策ではありますが、保守的すぎます。現在、共通鍵暗号の量子耐性強化に関する義務的な推奨事項はなく、AES-128やSHA-256などの128ビットセキュリティ強度のプリミティブは、現在および将来にわたって安全に使用できると考えられています。

情報理論的安全性への影響はあるか

情報理論的安全な手法(無条件の安全性、または完全な安全性とも呼ばれる)は、そのセキュリティの主張が数学的に証明されているアルゴリズム技術です。重要な情報理論的安全な構成やプリミティブの例として、バーナム暗号、シャミアの秘密分散、量子鍵配送(8)(耐量子暗号と混同しないよう注意)、エントロピー源および物理的複製防止機能(PUF)、ファジィコミットメントスキーム(9)などが挙げられます。

情報理論的な証明により、量子コンピュータを含めどのような計算能力を持つ攻撃者であってもセキュリティの主張を破るのに十分な情報を持たないことが示されるため、情報理論的安全な構成は量子脅威の影響を受けません。

Synopsys PUF:ポスト量子セキュリティの不確実性に対する解決策

Synopsys SRAM PUF

すべてのSynopsys PUF製品を支えるコア技術は、SRAM PUFです。他のPUFと同様に、SRAM PUFはシリコンチップの製造プロセスに起因する予測不可能なばらつきから生じる、デバイス固有の応答を生成します。SRAM PUFの動作は、事実上すべてのデジタルチップで容易に利用できる従来のSRAM回路に基づいています。

長年の継続的な測定と分析に基づき、シノプシスはSRAM PUFの挙動を非常に高い精度で記述する確率的モデルを開発しました(10)。これらのモデルを使用することで、SRAM PUFの予測不可能性に関する厳密な限界を導き出すことができます。この予測不可能性の限界はエントロピーの観点から表現される根本的なものであり、量子コンピュータをはじめとするいかなる量の計算能力をもってしてもこれを覆すことはできません。

Synopsys PUF 

Synopsys PUFは、SRAM PUF技術に基づくハードウェアセキュリティソリューションです。Synopsys HW PUFの中核コンポーネントは、SRAM PUFの応答でルート鍵を保護し、公開ヘルパーデータを生成するファジィコミットメントスキーム(9)です。ヘルパーデータはルート鍵に関する情報を一切開示しないことが情報理論的に証明されているため、ヘルパーデータが公開されているという事実がルート鍵のセキュリティに影響を与えることはありません。

この漏洩ゼロの証明は、何億ものデバイスにおける長年のフィールド展開を通じて維持されており、システムで使用されるPUFが、その確率的モデルによって示されるようにエントロピー源であることを前提としています。Synopsys HW PUFは、そのエントロピー源を使用してルート鍵を初めて初期化し、その後ファジィコミットメントスキームによって保護します。

ファジィコミットメントスキームとエントロピー源に加え、Synopsys HW PUFは、AESやSHA-256をはじめとする標準的な対称暗号プリミティブを用いた、認定された標準準拠の構成に基づく暗号化処理を実装しています(11)。これらの処理には以下が含まれます。

  • ファジィコミットメントスキームによって保護されたルート鍵を鍵導出鍵として使用する鍵導出関数(KDF)。
  • エントロピー源からの高いエントロピーを持つシードによって最初にシードされる、決定論的乱数発生器(DRBG)。
  • ファジィコミットメントスキームによって保護されたルート鍵から派生した鍵ラップ鍵を使用して、外部から提供されるアプリケーション鍵を保護するための、実質的に認証暗号化である鍵ラップ機能。

Synopsys Security IP:ポスト量子時代に向けた実績あるセキュリティ

Synopsys PUFのセキュリティアーキテクチャは、ルート鍵の生成と保護のための情報理論的安全なコンポーネントと、その他の暗号機能のための確立された対称暗号に基づいて構築されています。情報理論的安全な構成は、量子攻撃に対して耐性があります。対称暗号に対する量子脅威の影響は限定的であり、現時点でも将来においても対策を講じる必要はありません。重要な点として、Synopsys PUFは、量子脆弱性を持つ公開鍵暗号プリミティブを一切使用していません。

Synopsys PUFのすべてのバリアントは量子耐性を備えており、推奨されるポスト量子ガイドラインに準拠しています。256ビットセキュリティ強度バリアントのSynopsys PUFを使用することで、遠い将来においても強力な耐量子性が提供されますが、128ビットバリアントについても、現在および予見可能な将来において完全に安全に使用できると考えられています。 

 

リファレンス

  1. “Report on Post-Quantum Cryptography”, NIST Information Technology Laboratory, NISTIR 8105, April 2016, https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
  2. “2021 Quantum Threat Timeline Report”, Global Risk Institute (GRI), M. Mosca and M. Piani, January, 2022, https://globalriskinstitute.org/mp-files/quantum-threat-timeline-report-2021-full-report.pdf
  3. “PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates”, NIST Information Technology Laboratory, July 5, 2022, https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
  4. “Grover’s quantum searching algorithm is optimal”, C. Zalka, Phys. Rev. A 60, 2746, October 1, 1999, https://journals.aps.org/pra/abstract/10.1103/PhysRevA.60.2746
  5. “Reassessing Grover’s Algorithm”, S. Fluhrer, IACR ePrint 2017/811, https://eprint.iacr.org/2017/811.pdf
  6. “NIST’s pleasant post-quantum surprise”, Bas Westerbaan, CloudFlare, July 8, 2022, https://blog.cloudflare.com/nist-post-quantum-surprise/
  7. “Post-Quantum Cryptography – FAQs: To protect against the threat of quantum computers, should we double the key length for AES now? (added 11/18/18)”, NIST Information Technology Laboratory, https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs
  8. “Quantum cryptography: Public key distribution and coin tossing”, C. H. Bennett and G. Brassard, Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, December, 1984, https://arxiv.org/abs/2003.06557
  9. “A fuzzy commitment scheme”, A. Juels and M. Wattenberg, Proceedings of the 6th ACM conference on Computer and Communications Security, November, 1999, https://dl.acm.org/doi/pdf/10.1145/319709.319714
  10. “An Accurate Probabilistic Reliability Model for Silicon PUFs”, R. Maes, Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, 2013, https://www.iacr.org/archive/ches2013/80860176/80860176.pdf
  11. NIST Information Technology Laboratory, Cryptographic Algorithm Validation Program CAVP, validation #A2516, https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/details?validation=35127
Ask BETA This experience is in beta mode. Please double check responses for accuracy.

チャットを終了する

このウィンドウを閉じると、チャット履歴が消去され、セッションが終了します。本当に このチャットを終了してもよろしいですか?