Quantum Business Magazine

コラム:2022年の展望 量子インターネット ② 量子暗号:NISTの標準化プロセスの状況

Quantum Business Magazine a year ago


by David Shaw, Fact Based Insight


この記事は許可を得て再掲載しています。オリジナルは、こちら からFact Based Insightのウェブサイトを確認のこと。


2022年の展望 量子インターネット ① 差し迫った脅威



 


【 ポスト量子暗号はターニングポイントを迎える 】


2006年から、量子的な攻撃に強い、新たな数学的暗号プロトコルの開発は進められてきた。2016年からはNISTが中心となり、量子耐性に優れたPQC DS(電子署名)およびPQC KEM(鍵カプセル化機構)プロトコルの標準化に向けた評価プロセスが進められている。



NIST PQCプロセス -

ラウンド1では、69の候補が評価され、そのうち21が破損または重大な攻撃を受けた。

ラウンド2では、26の候補が強度を計られ、そのうち8つが攻撃を受けた(いくつかは完全に壊れ、いくつかは軽微)。

ラウンド3では、7つの最終候補の評価が完了し、1つは重大な攻撃を受けた。


NISTは2022年の早い時期に、どのプロトコルを新しい規格の基礎として使用するかを発表する予定だ。ドラフトは2022年にパブリックコメントのために掲載され、2024年に最終決定される予定である。[2]


KEM/公開鍵暗号方式のファイナリストは、NTRU、CRYSTALS-KYBER、SABER、Classic McElieceとなっている。初めの3つは構造化された格子ベースのスキームであり、セキュリティとパフォーマンスのトレードオフが良好だ。従来のインターネットセキュリティの代替品として適しているだろう。NISTは最終的にこのうちの一つを標準化する予定だ。Classic McElieceは、非常に短い暗号文サイズながら、とても長い公開鍵(262kバイト!)を提供するという、まったく違ったプロファイルを持ったものだ。30年以上も攻撃から逃れてきたものとは、別のコードベースのスキームであることが重要であるとしている。


デジタル署名のファイナリストは、FALCON、CRYSTALS-DILITHIUM、Rainbowだ。最初の2つが構造格子をベースにしていて、NISTは最終的にどちらを選択する予定となっている。Rainbowは多変量解析方式で、最終候補を多様なものとしてるが、鍵サイズが非常に大きいため、汎用アルゴリズムとしては不向きかもしれない。UK Leuven [3]の研究がRainbowの表向きの安全性であることを指摘し、作者はパラメータモデルを調整せざるを得なくなるなど、さらに打撃を受けることになった。


KEMの代替候補を見ていこう。BIKEは効率的な構造化ベースのスキームであり、格子ベースのスキームが失敗した時にインターネットをバックアップする可能性を持っている。HQCは別のコードベース方式で、性能は劣るもののセキュリティ強度が高いかもしれない。SIKEは等値性ベースで、帯域幅の特性は良いのだが、処理のオーバーヘッドが大きい。NTRU Primeは格子ベースの方式だが、ことなる構造の過程に依存している(復号の失敗とサイクロトミックを避けることができる)。FrodoKEMは、非構造格子ベースの方式で、性能は大きく低下するのだが、とても高い安全性が約束されている。


続いてはDSの代替候補を。GeMSSは多変量解析に基づく方式だが、セキュリティ上の懸念が残る。Picnicは、対称暗号ベースの方式セキュリティでより強力だ。SPHINCS+も対称ハッシュベースであり、これが最も強力なPQC署名を提供すると思われる。


現在当然のことながら、多くの人が先行プロセスの迅速かつクリーンな終了を望んでいる。しかしNISTにとって標準化は、難しいバランスのとれた行為でなければいけないのだ。構造格子暗号は、以前からNISTプロセスにおける有力候補であると目されてきた。設計上、セキュリティと性能はトレードオフの関係にあるのは知られている。NISTのプロセスで、これらの要件が比較検討され、最終的に選択された方式は、将来の日常的なセキュリティにおいて中核を形成することになるだろう。



格子暗号技術 -

格子上で定義された問題の計算が困難であることに基づき、1996年に発表された技術。最も強力にした実装では、最短ベクトル問題の、最も複雑なものと同等の困難さがあることを示すことができる。古典でも量子でも、それに限らず有効な攻撃は知られていない二面体群の隠れた部分群問題を解くことにつながっていく。[4]


構造格子 -

日常的なインターネットやビジネス利用などを想定した性能要件を満たすため、暗号技術者は一般的に、「構造格子」の利用を提案している。これは理論的な安全性の一部と引き換えに、鍵のサイズを小さくして処理速度を向上させるためだ。


懸念を表明する著名な声もある。この手法に詳しくない場合、本当のリスクバランスを理解していない可能性がある、と指摘している。


NTRU Prime(代替リストに掲載されているプロトコル)チームは、「NIST PQCプロジェクトで検討されている格子ベースのKEMは、一般に考えられているよりもはるかにリスクが高い」という見解を表明し、そのうえで自分たちのアプローチ(異なるタイプの構造格子)には、具体的な防御上の利点があると語っている。[5]


同時にまた、NTRU Primeは中立的な立場でないことを指摘する声もある。Fact Based Insightは、最も判断に重要なこととして、NISTのプロセスが、リアルな量子暗号解読に対してどれだけ有効性を示せるか、ということだ。ここまで成功した攻撃のほとんどは、古典的なアプローチ(サチュレーション、ふるい分け、MinRank攻撃など)の延長戦上にあった。それらが最初の切り口であることに異論はないが、実現可能な確認手法としての限界である点も確かだ。



不本意ではあるが、特許権に関する議論も最終的な選考に大きく影響を与えている。この問題は、コミュニティの中で感情的になりやすい問題だ。


特許について -

CRNSは、NISTの構造格子の最終候補であるKyberとSABERは、CRNSが持つ特許(US 9094189B, EP 2537284)の範囲に含まれると主張し続けている。KyberとSABERの両チーム(いずれもフランスが主導/参加)はこの主張に対し、数学的な根拠を持って反論している。本来この問題は、数学的なことではなく、将来の特許裁判所がどのような判決を下すかであり、科学的というより法的な問題なのである。


NISTとCRNSの間で、この問題を解決するための交渉が、コストをめぐって行き詰っている。ビジネスでは、交渉を行えばそれなりに解決するものだと考える人が多いかもしれない。しかし、PQCフォーラムを良く知る人なら、暗号コミュニティではこの問題で感情が高ぶり、その大部分がIPフリーでぶつかり合っていることを知っているはずだ。特に技術的な理由で特許が適用されないとなれば、CNRSに何かを支払うことは悪い前例になってしまう、と主張する人もいる。皮肉なことに、NISTのプロセスで最も損をするのは、フランス勢が多く参加する2つの企業なのだ。現在60人のコミュニティメンバーが署名した書簡がCRNSに送られ、立場を変更するよう求めている。[6]


概して言えば、将来起こりうる起訴に対する不確実性が、商業的な展開の前に大きな障壁となっているのだ。さらにNISTにとって大きな問題は、最終的な選定が完全に非技術的な懸念に左右されていると見られた場合、コミュニティ内でのNISTの信頼を損なう可能性があるということだ。そこで、複数の構造格子型KEM法を標準化しようというアイデアも出ている。



バックドアへの不安 -

NISTが、バックドアや既知の脆弱性を持つプロトコルを故意に承認することがあるとは誰も思わないだろう。しかし、情報機関(NSA、GHCQ、DGSEなど)がプロセスに介入したり、密かに知られている脆弱性の知識を共有しなかったりすることは、普通に考えられると思わないだろうか?多くの人が、過去にはこのようなことが起こったと考えているが、NISTはその後、選定プロセスを大幅に強化しているのだ。[7]


NISTのDustin Moody氏は、次のように強調する。「NISTだけで決定しており、NSAを我々の標準化プロセスから遠ざけている。あらゆる重要な利害関係者からのコメントを受け入れるのと同じように、彼らからのコメントを受け入れている」と。


Fact Based Insightは、NISTにこれ以上何ができるのか、実際のところわからない。この懸念の重要度をどのように評価するかは、おそらく個人の世界観の問題と相関することになるだろう。中国は、すでに独自のPQC選考を実施し、終了している。


実際には、これらの議論に関わっているすべてのグループが、格子暗号の大きな可能性を信じている。これ以上コミュニティの活動状況をどう判断できるだろうか?


PQCの提出に直接関与してはいないが、政府の情報機関において長い経験を持つcyrptoの古株は、「PQCの議論には、多くの有識者がいる。発表された中には、自分勝手なものもあると思う。もちろんNISTはすべて把握しているだろう。しかし、どのみち彼らは内部の意見ではなく、コミュニティや提出物、報告書などに基づいて、最後には自分たちの決定を正当化する必要があるだろう」と述べている。


Fact Based Insightは、PQCフォーラム[8]で見られた礼節を欠く行為に対して、誰もが一線を引く必要があると考えている。不統一は、ビジネス界を混乱させ、素晴らしい技術の採用を遅らせる危険性があるだろう。私たちは、NISTが困難なプロセスを、難しいスケジュールで、うまく運営してきたと評価している。NISTの決定は、これらの問題と、実装可能性・移行に対し十分間に合うようにするためのリスクが、常にトレードオフにならざるを得ないことは、ずいぶん前からわかっていたことだ。企業は自信をもってその勧告にしたがうべきだと私たちは信じている。



各種問題に対する多様性が必要


性能面でのトレードオフが一般と異なり、より強力なPQCを求める企業ユーザーは、PQCの追加規格の登場をより長く待つ必要がある。NISTのPQCラウンド4における、代替案の継続的な評価が、このギャップを埋めるのに役立っていくことになる。まったく発展途上の分野であり、多様性の確保が大事である。将来、あるプロトコルやプロトコル群に弱点が発見された場合、その代替手段も準備しておかなければならない。


構造格子暗号は、新世代のインターネットセキュリティにおいて、標準のベースになるものであると期待できる。大きな懸念があったにもかかわらず、このように機能するプロトコルがあることは、とても明るい材料だ。しかしこの「ベストケース」の選定は、これまでの経験則という狭い道筋に依存していることに留意しておかなければならない。


最も懸念されているのは、構造格子に基づく電子署名方式に代わる汎用的なインターネット互換の方式がまだ存在しないことだ。このことは、新しい量子攻撃や従来の攻撃に対する単一障害点となる可能性があることを意味している。NISTは、このリスクギャップを埋めるために、PQCコミュニティに対して、さらに提案募集を行うことを決定している。



移行はさらに大きな課題


当然ではあるが、正式な規格が完成する前に、これらの新しいアプローチを事業展開することには注意しなければいけない。とはいえ、標準化文書に選ばれたプロトコルの知識は、活動のターニングポイントとなることが予想される。


知っての通り、インターネットは野蛮で多様な場所だ。すべてのプロトコルやハードウェア(特に古いハードウェアや古いアプリケーション)が、新たに必要となるより大きな鍵のサイズや、オーバーヘッドでスムーズには機能しなくなるだろう。移行準備とテストは、多くの企業にとって、とても困難な問題とし降りかかってくる。増え続けるIoT機器には、軽量化や省電力化を優先して、セキュリティ性能への対応を先延ばしにする危険な誘惑が待っているだろう。


NIST NCCoEは、この移行を計画し実行する企業を支援するため、「Migration to PQC」プロジェクトをスタートしている。これは非常に重要なステップである。今日のハッキングの大半は、基礎となるプロトコルではなく、実装の脆弱性を攻撃するものだからだ。量子安全プロトコルへの移行を急いだり、熟考を欠いたりすると、かえってこの状況を悪化させる可能性があると考えてほしい。[9]


この20年間で、暗号のセキュリティに対する理解は全体的に進んできた。セキュリティは、「目的地というよりも、旅である」ということが明確に認識されるようになった。ほとんどの企業は、現在構築しようとしているシステムの中心に暗号の俊敏性を据えるだろう。


暗号ブーム –

PQCの移行活動は、サイバーセキュリティ・サービス・プロバイダーにとって大きなビジネスとなることが期待されている。


NISTのPQCプロセスには、IBM、Microsoft、Atosなどのメジャー企業が深く関与している。PQShield、PQSecure、CrypotoNext、ISARAなど、多くの専門企業が、NISTスイートのアルゴリズムの実装を支援する体制を整えている。


Quantropiは、独自のPQCソリューションQiSpaceを提供している。独自の多変量PQC KEMであるMASQと、独自の「量子順列パッド」技術[10]を含んでいる。これは、量子計算の構造にヒントを得て、古典的なプロセッサで実装されたものだ。対称型暗号QEEPの基礎として、また擬似QRNGを提供するために使用されてる。Post-Quantumは、アイデンティティとセキュアなアプリケーションに焦点を当てている。また、EvolutionQは、PQCと量子暗号からの洞察を提供するというユニークな立場にある。


量子への移行後に戦略に着手しようとしている企業は、もっと早く行動を起こしていればよかったと思うかもしれない。専門家というのは希少な存在であり、今後ますますその傾向が強まることが予想できる。


【③に続く】



References


[2] “CSRC Presentation: Status Update on the 3rd Round | CSRC,” CSRC | NIST, 07-Jun-2021. [Online]. Available: https://csrc.nist.gov/Presentations/2021/status-update-on-the-3rd-round . [Accessed: 02-Nov-2021]

[3] W. Beullens, “Improved Cryptanalysis of UOV and Rainbow,” 1343, 2020 [Online]. Available: https://eprint.iacr.org/2020/1343 . [Accessed: 05-Dec-2021]

[4] D. Micciancio and O. Regev, “Lattice-based Cryptography,” p. 33.

[5] “ROUND 3 OFFICIAL COMMENT: NTRU Prime.” [Online]. Available: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/nH1inZ24sYY/m/lFK179lUBgAJ . [Accessed: 20-Nov-2021]

[6] “Quand un brevet perturbe l’innovation postquantique,” Le Monde.fr, 16-Nov-2021 [Online]. Available: https://www.lemonde.fr/sciences/article/2021/11/16/quand-un-brevet-perturbe-l-innovation-postquantique_6102215_1650684.html . [Accessed: 06-Dec-2021]

[7] “NIST Removes Cryptography Algorithm from Random Number Generator Recommendations,” NIST, 21-Apr-2014. [Online]. Available: https://www.nist.gov/news-events/news/2014/04/nist-removes-cryptography-algorithm-random-number-generator-recommendations . [Accessed: 14-Dec-2021]

[8] “pqc-forum – Google Groups.” [Online]. Available: https://groups.google.com/a/list.nist.gov/g/pqc-forum . [Accessed: 14-Dec-2021]

[9] “NIST NCCoE.” [Online]. Available: https://www.nccoe.nist.gov/ . [Accessed: 14-Dec-2021]


Quantum Business Magazine

@qbm

米国のQuantumComputingReportからの翻訳記事にオリジナルの量子業界の記事を加えてお届けしています。

quantumbizmag

© 2022, blueqat Inc. All rights reserved