Octo Knot(オクトノット)｜量子コンピュータが解読する暗号通信！次世代の格子暗号とその仕組み

量子コンピュータと暗号技術のあぶない関係

量子コンピュータとは、現在広く利用されているコンピュータとは異なり、量子力学の原理を利用したコンピュータです。2019年には、スパコンを使っても1万年かかるため実質的に解けない問題を、量子コンピュータを使い200秒で解くなど、これまでのコンピュータでは実現不可だったことができるようになることが示されています[1]。

Octo Knot(オクトノット)｜21世紀のほこ×たて!? 量子コンピュータとセキュリティの未来　

既存のコンピュータよりも圧倒的な処理速度を持つことで、社会や経済を大きく変えると言われている「量子コンピュータ」。その一方で、量子コンピュータの登場によって、現状のデータ暗号化技術が脅威にさらされる可能性も指摘されています。まさに『ほこ×たて』とも言える両者は、今後どうなっていくのか。量子コンピュータの開発を担当するNTTデータの矢実貴志さんと、金融業界の暗号セキュリティの専門家であるNTTデータの阿久沢佑介さんの2人が語り合いました。

量子コンピュータの歴史は意外と古く、1980年代からその仕組みが議論されています。1994年には「ショアのアルゴリズム」が提案され、量子コンピュータを使うことで素因数分解を効率的に行えることが示されました。素因数分解は、現在のインターネット上の暗号通信（https）でも広く利用されているRSA暗号でも利用されています。

ただし、RSA暗号を解くには、ショアのアルゴリズムと大規模な量子コンピュータが必要となります。現時点で実現している量子コンピュータの規模では暗号解読にはいたりません。大規模な量子コンピュータが実現するのは2030年以降と見られています。それまでに新しい暗号方式への切り替えが完了していれば、基本的には（※）量子コンピュータによる暗号解読は脅威ではありません。

※ 現在の暗号データを長期保存し、量子コンピュータが実用化された20年後などに解読する攻撃手法が考えられますが、これが脅威となるのは20年後も価値を持つ情報に限ります。

大規模な量子コンピュータの実現により、暗号通信が解読される

処理可能な量子ビット数が多い大規模な量子コンピュータの実現による影響が心配されているのは、主に公開鍵暗号となります。ショアのアルゴリズムを使うことで、これまではスパコンを使っても解読に1億年かかっていたRSA暗号が、量子コンピュータでは24時間以内で解読できるようになると言われています。AES（※）を代表とする共通鍵暗号は、量子コンピュータを使っても公開鍵暗号ほど効率的に解く方法が見つかっていません。量子コンピュータによる影響は軽微と見られており、これまで通りの方式で暗号鍵を長くする程度で問題ないと考えられています。

（※）Advanced Encryption Standard。NISTが2001年に標準化した共通鍵暗号。ファイルが第三者に読み取れないように、パスワードを使って暗号化する場合などに利用される。

公開鍵暗号はhttpsなどの暗号通信に使われています。インターネットでショッピングをする場合を例にとると、クレジットカード情報など大事な情報を盗ませない、ショッピングをしているサイトが偽サイトでないことを保証するなど、今日のインターネットにはなくてはならない技術となっています。
現時点で大規模な量子コンピュータが実現すると、現在の暗号通信が解読されてしまう懸念があるため、インターネットが安心して使えなくなってしまいます。

次世代の「耐量子暗号」標準化に向け準備が進められている

大規模な量子コンピュータの実現に備え、米国のNIST（※）は、2016年から量子コンピュータでも解読が困難な新しい暗号方式の標準化に向けた活動を開始しました[2]。このプロジェクトは、大規模な量子コンピュータの実現を見据え、2030年までに新しい暗号方式へ切り替えることを目標に活動しています。
このプロジェクトの成果は、事実上の世界標準として扱われることになります。このプロジェクトの成果として、2024年に新しい暗号方式が標準化され、2030年までに新しい暗号方式へ切り替えが行われる計画です。

※National Institute of Standards and Technology。米国立標準技術研究所。アメリカ政府の調達におけるセキュリティ基準などを定めており、暗号方式の標準化においては事実上の世界標準として扱われる。

耐量子計算機暗号へのアルゴリズム移行時の留意点は？ | NTTデータ | DATA INSIGHT | NTTデータ - NTT DATA

2022年7月5日、米国政府機関で耐量子計算機暗号（PQC）の標準技術が選出された。そろそろ、既存暗号アルゴリズムのPQCへの移行計画を検討すべき時期が近付いてきた。しかし、どのような点に気を付けて移行計画を立てるべきだろうか？

この新しい暗号方式を、「耐量子暗号」（PQC：Post-Quantum Cryptography）または「耐量子計算機暗号」といいます。耐量子暗号は、量子コンピュータでも容易に解読できないのは当然として、現在のコンピュータでも解読できない新しい暗号方式となります。

「格子暗号」は、耐量子暗号の主要な方式の1つ

NISTの耐量子暗号の標準化プロジェクトは2016年に募集が開始され、82の暗号方式の応募がありました。その後、ラウンド1、ラウンド2と検討が進められ候補が絞られました。標準化の一歩手前であるラウンド3開始時には15候補が残りました。うち約半数の7候補が格子問題を元にした格子暗号です[3]。

その後、2022年7月にはラウンド3の検討が完了し、格子暗号の中から標準化される暗号方式が3つ選定されました[4]。格子暗号以外からも1つが標準化に選定されています。格子暗号以外で残った候補のうち4つはラウンド4として継続検討されるとともに、デジタル署名の暗号方式の追加募集が行われています[5][6]。標準化に選定された暗号方式は、引き続き最終調整が行われ2024年には正式に標準化される予定です。

耐量子暗号は、安全性評価の観点でまだ歴史の浅い暗号であるため、今後耐量子暗号が破られる可能性が考えられます。実際、ラウンド3に残った15候補のうち2つは、2022年時点で容易に解読できるケースが確認されています。このように暗号が実質使えなくなる場合に備えるため、NISTは格子暗号を含め複数の方式を標準化する方針としています。格子暗号以外の暗号方式はラウンド4などを経て、追って標準化される見込みです。

図1：耐量子暗号の標準化概況

暗号方式の世代交代、耐量子暗号への切り替え

耐量子暗号への切り替えについて考えてみます。現在の暗号が解読できる規模の量子コンピュータが実現されるのはまだ先と見られています。量子コンピュータの専門家へのアンケート結果を見ると、現在の暗号が解読できる量子コンピュータが実現されるのは、2037年頃というのが1つの目安となりそうです（※）[7]。ただし、技術的な革新が発見された場合など、この見込みが前倒される可能性もあるため、継続的に技術動向を把握する必要があります。

（※）量子コンピュータの専門家40人へのアンケート結果より、現在の暗号が解読できる量子コンピュータができる可能性が50%以上、と考える専門家の数が過半数を超えるのは15年後（2037年）。

また、量子コンピュータの実現とは別に、コンピュータの処理性能の向上により、現在使っている暗号の強度が不足することが見込まれています。アメリカのNISTおよび日本のCRYPTREC（※）は、現在主流であるRSA2048bitは、近い将来に暗号強度の不足が見込まれるため、2030年までに原則利用を停止するよう定めています[8][9]。そのため、現在の暗号の利用停止と合わせ、2030年までに耐量子暗号への切り替えが進むことになると考えられます。

※総務省、経済産業省、国立研究開発法人情報通信研究機構、独立行政法人情報処理推進機構の4機関からなるCRYPTREC（Cryptography Research and Evaluation Committees）事務局が運営する団体。

日本ではCRYPTRECがまとめた電子政府推奨暗号リストの改定が、2023年3月頃に行われる予定です。耐量子暗号については、2023年時点では標準化が完了していないため電子政府推奨暗号リストには載らないものの、別途ガイドラインが公開される予定です。

一般利用者は切り替えを意識する必要はない

システムを利用する側である一般利用者は、耐量子暗号への対応に関して特に意識する必要はありません。

インターネットを利用する際に使うChrome、Edge、Safariといったブラウザの自動アップデートにより、意識せずとも耐量子暗号への切り替えが完了します。2018年に標準化された暗号化通信プロトコルTLS1.3への対応実績を見ると、標準化されてから数か月程度で対応が完了しているため、耐量子暗号への対応も2025年には完了しているものと考えられます。耐量子暗号対応によるCPU等への負荷増についても、ユーザの体感するレベルではほとんど影響しない見込みです。

システム管理者は2030年までに計画的な切り替えが必要となる

システムを提供する側については、2025年から2030年の間に耐量子暗号への切り替えを完了させる必要があります。システムは、おおむね5年おきに刷新する場合が多いですが、影響確認などを考えるとこの刷新タイミングに合わせて、耐量子暗号への切り替えを行うことが最善と考えられます。

商用システムでは、暗号通信の実現にロードバランサ製品を利用している場合が多いです。主要なロードバランサ製品がTLS1.3に対応した実績を見てみると、標準化されてから1年程度を要しています。耐量子暗号への対応もこれと同程度と考えると、耐量子暗号へ対応した製品が出そろうのは、標準化が完了してからおよそ1年後、2025年頃となると考えられます。

図2：耐量子暗号への切り替え期間

格子暗号はどのように暗号化しているのか

格子暗号は耐量子暗号の主要な方式の1つです。格子暗号でなぜ安全に秘密の情報が送れるのか、その仕組みについてひも解いてみます。ただし、格子暗号をかなり単純化して表現している点についてはご留意ください。

格子点とは、規則的に並ぶ点のこと

格子は、日常でも障子や格子戸などで見られる構造で、基本図形が規則的に並ぶパターンが見られます。このパターン区切りの交点を「格子点」と呼びます。格子暗号では、この格子点を数学的に表現し、暗号に利用します。

図3：格子、格子点、基本図形のイメージ

ここで、格子点の特性についてまとめてみます。ここでは、イメージしやすいように、平面（2次元）に並ぶ格子点で考えてみます。

すべての格子点は、基本パターンの組み合わせで表現できます。図4の通り、基本パターンを「右に1」と「上に1」とすると、すべての格子点はこの組み合わせ、すなわち基本パターンの整数倍で表現できます。

図4：格子点と基本パターン

この特性を整理すると、以下の3点が言えます。
　・基本パターンがわかれば、すべての格子点がわかる
　・格子点がわかれば、「ある点が格子点なのか」がわかる
　・格子点がわかれば、「ある点に最も近い格子点」がわかる

図5：格子点の特性

格子問題とは、一部の格子点から基本パターンを推測するのが難しいこと

格子暗号の元となる格子問題とは、「一部の格子点から基本パターンを推測するのが難しいこと」を言います。いくつかの格子点がわかっていれば、簡単に基本パターンが見つけられそうですが、格子問題は後述するようにちょっと工夫することで格段に難しくすることができます。

図6：格子問題のイメージ

格子点は、直交させずに斜めに並べることができます。これが格子問題を格段に難しくするちょっとした工夫の1つです。先の図4から図6の例では、右方向と上方向を分けて考えることができましたが、斜めに並べると2つの方向を同時に考える必要があります。

図7：格子点を斜めに並べた場合

格子点は、2次元に限らず、3次元、4次元と次元を増やすことができます。これも、格子問題を難しくする工夫の1つです。2次元の場合は2方向だけ考えれば良かったのですが、例えば100次元になると100方向を同時に考える必要があります。

図8：格子点を3次元に並べた場合

格子暗号は、格子点に誤差を加えて秘密の情報を送る

格子問題は、いくつかの格子点からすべての格子点（基本パターン）を推測することが困難な問題でした。実際の格子暗号では、さらに格子点に誤差（エラー）を加えることで、推測を難しくしています。これも格子問題を格段に難しくするちょっとした工夫です。

ここでは、アリスとボブが以下の手順で暗号文をやり取りする例で考えてみます。

1. アリスからボブに、公開鍵を送る
2. ボブからアリスに、公開鍵で暗号化した秘密の情報を送る
3. アリスは、秘密鍵で復号し、秘密の情報を取り出す

図9：ボブからアリスへ秘密の情報を送るイメージ

1. アリスによる公開鍵の作成

アリスは、ボブが暗号文を作成するための公開鍵を作ります。公開鍵に相当するのは「誤差を含む格子点の情報」、秘密鍵に相当するのは「格子点の基本パターン」となります。

　① 格子点（基本パターン）を準備する
　② いくつかの格子点を選ぶ
　③ 選んだ格子点に誤差を加える

ここで加える誤差はプラスの値、すなわち格子点から少し奥にはみ出るように誤差を加えます。また、誤差は軽微で、元の格子点から大きく外れないようにする必要があります。

このように誤差を加えた点の情報を、公開鍵としてボブに送ります。また、格子点と格子点の間隔の広さについても、ボブに送ります。

図10：アリスによる公開鍵の作成

2. ボブによる暗号文の作成

ボブは、アリスから受け取った公開鍵を使って、暗号文を作ります。ボブは、格子点の基本パターンを知らないため、実際の格子点を推測することはできません。アリスから受け取った誤差を含む格子点の情報を使って、暗号文を作成します。

　① アリスから受け取った点から、いくつかの点を選ぶ
　② 選んだ点を合算する
　③ 合算した点に、送る情報bを加える

②について、アリスから受け取った点は「軽微な誤差を含む格子点」のため、その点を合算した点も「軽微な誤差を含む格子点」となります。
③で送る情報bは、ボブが送りたい秘密の情報に基づいて以下の条件に従い決定します。ただし、秘密の情報は0または1の1ビットの情報となります。
　・0を送る場合、0
　・1を送る場合、格子点の間隔の半分
この結果、1を送る場合は、格子の間隔の半分だけ奥にずれた点が得られます。

③で得られた点を暗号文としてアリスに送り返します。

図11：ボブによる暗号文の作成

3. アリスによる復号

アリスは、ボブから受け取った点から、ボブの送った情報が0なのか1なのかを取り出します。アリスは格子点の基本パターンを知っているため、最寄りの格子点を探すことができます。ボブから受け取った暗号文の点と、最寄りの格子点の位置関係より、ボブが送った情報が0なのか1なのかを判別することができます。

誤差はプラスの軽微な値であったため、最寄りの格子点が手前にある場合は、ボブの送った情報は0と判断できます。

　① 最寄りの格子点が手前にある場合、ボブが送った情報は0
　② 最寄りの格子点が奥にある場合、ボブが送った情報は1

共通暗号鍵など、多くのデータを送る場合は、このやり取りを繰り返すことで実現できます。

図12：秘密の情報の取り出し

おわりに

量子コンピュータは、その計算能力の高さから、これまでできなかった計算ができるようになることが期待されています。一方で、暗号技術においてはその計算能力の高さにより、暗号が解読されるリスクが見込まれています。幸いにも、そのリスクが顕在化するタイミングはまだ先であり、それに向けた準備も進んでいるため、特段心配する必要はありません。

新しい暗号である耐量子暗号は、2024年には標準化され、その後2030年までに広く使われるようになる見込みです。一般利用者は、ソフトウェアの自動アップデートにより、いつの間にか新しい暗号を使うことになるため、耐量子暗号への切り替えは特段意識する必要はありません。

このように、セキュリティの領域では将来起こるリスクに対し先だって対策を行っており、気づかず守られている場合が多くあります。日々のインターネットの利用でトラブルが起きていないことは、実は当たり前のように適切なセキュリティ対策が施されているのです。暗号をはじめとするセキュリティ技術がインターネット社会を影で支える重要な役割を果たしていることをご理解いただけると幸いです。

引用文献
本文中に引用した文献は下記になります。

[1] Quantum supremacy using a programmable superconducting processor
https://www.nature.com/articles/s41586-019-1666-5
https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html

[2] Post-Quantum Cryptography
https://csrc.nist.gov/Projects/post-quantum-cryptography

[3] Round 3 Submissions
https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions

[4] Selected Algorithms 2022
https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022

[5] Round 4 Submissions
https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions

[6] Post-Quantum Cryptography: Digital Signature Schemes
https://csrc.nist.gov/Projects/pqc-dig-sig

[7] 2022 Quantum Threat Timeline Report
https://globalriskinstitute.org/publication/2022-quantum-threat-timeline-report/

[8] SP 800-57 Part 1 Rev. 5
Recommendation for Key Management: Part 1 – General
https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final

[9] 暗号強度要件（アルゴリズム及び鍵長選択）に関する設定基準
https://www.cryptrec.go.jp/list/cryptrec-ls-0003-2022.pdf

※本記事の内容は、執筆者および協力いただいた方が所属する会社・団体の意見を代表するものではありません。
※本文および図中に登場する商品またはサービスなどの名称は、各社の商標または登録商標です。
※記事中の所属・役職名は取材当時のものです。

量子コンピュータが解読する暗号通信！次世代の格子暗号とその仕組み

目次