1．は　じ　め　に

　公開鍵暗号として広く普及しているRSA暗号は，素因数分解問題の困難性を安全性の根拠としている．素因数分解問題を効率的に解く研究は大規模な計算機実験も含めて活発に行われてきた．現在最も漸近的に高速なアルゴリズムとして数体ふるい法が知られており，合成数の桁長に対して準指数時間の計算量が必要となる．例えば，現在利用される2,048ビットの合成数を数体ふるい法で素因数分解するためには，10²⁷FLOPSのスーパコンピュータを1年間占有する計算量が必要と見積もられている．最も高速なスーパコンピュータのLinpack性能は10¹⁸FLOPSであり，2,048ビットの素因数分解にはムーアの法則を仮定しても今後数十年以上は必要となる⁽¹⁾．

　ところが，1994年にショアは，量子計算機を用いることにより素因数分解が高速に実行可能なアルゴリズムを発表した⁽²⁾．ショアの量子アルゴリズムの計算量は合成数の桁長に対して多項式時間であり，数体ふるい法から指数関数的なスピードアップを達成している（図1）．つまり，量子計算機を用いると，合成数の桁長を大きくしたとしても，素因数分解問題の困難性は大きく増加しないことになる．このような状態は暗号の危殆化と言われて，RSA暗号は量子計算機により理論的には解読された状態となっている．

　更に，ショアの論文では，だ円曲線暗号の安全性を支える離散対数問題に対しても，量子計算機を用いて高速に解読可能となるアルゴリズムを発表している．つまり，大規模な量子コンピュータが実現すると，現在我々が利用しているRSA暗号及びだ円曲線暗号が危殆化する状況にある．そのため，量子計算機を用いても解読が困難となる数学問題を利用した耐量子計算機暗号（PQC: Post-Quantum Cryptography）の研究開発が活発に行われている．

2．耐量子計算機暗号

　素因数分解問題や離散対数問題とは異なる計算問題を利用した公開鍵暗号の研究は，RSA暗号が発表された1970年代後半から既に開始されてきた．実際，誤り訂正符号の性質を利用したMcEliece暗号は1978年に提案されている．1982年にはハッシュ関数の一方向性や衝突困難性を安全性の根拠とするMerkle署名が発表された．また，1980年代前半から，有限体上の多変数多項式求解問題（MQ問題）の困難性を基にした多変数多項式暗号が研究されるようになる．更には，1990年代後半から，NTRU暗号など格子理論を利用した暗号が提案され，2005年にはLearning with Errors（LWE）問題に基づく暗号が発表された．これらの暗号の安全性は，格子の基底に対して非零最短ベクトルを求める問題（SVP）に基づいているため格子暗号と言われる．また，1990年代後半から同種写像暗号のアイデアが発表され，2006年には超特異だ円曲線の同種写像の列で構成されるラマヌジャングラフの計算困難性を基にした暗号も提案された．

　また，これらの代表的な数学問題は，2016年に米国標準技術研究所NISTが発行した報告書NIST-IR 8105（https://doi.org/10.6028/NIST.IR.8105）にも，耐量子計算機暗号の主要な候補として記載されている．表1に，これらの代表的な耐量子計算機暗号とそこで使われている数学問題をまとめた．

　これらの流れを受けて，2006年から耐量子計算機暗号を専門とする国際会議Post-Quantum Cryptography（PQCrypto）がスタートした．更に，2015年4月には，米国標準技術研究所NISTにより，NIST Workshop on Cybersecurity in a Post-Quantum Worldが開催された．2015年以降は，耐量子計算機に特化したワークショップや国際会議が数多く開催されるようになる．特に，2016年2月には，筆者がプログラム委員長を務め，九州大学西新プラザにおいて第7回目のPQCrypto 2016を主催した⁽³⁾．PQCrypto2016では，NISTから耐量子計算機暗号の標準化の具体的な計画が示されて，参加者が240名を超えるなど，会場は熱気に包まれた状態であった（図2）．

3．NIST PQC標準化プロジェクト

　2015年8月にアメリカ国家安全性保障局NSAは耐量子計算機暗号への移行を表明し，2016年2月には米国標準技術研究所NISTが耐量子計算機暗号の標準化計画を発表した．NISTの耐量子計算機暗号の標準化では，公開鍵暗号プリミティブを対象として，SP 800-56，FIPS PUB 186-4で規格化されている暗号方式（Public-key Encryption），鍵交換方式（Key Exchange），ディジタル署名（Digital Signature）の耐量子版の公募を行った．NISTによる耐量子計算機暗号の標準化に関する情報は，NIST Post-Quantum Crypto Projectのホームページ（http://nist.gov/pqcrypto）で入手可能である．

　最初に，標準的な安全性評価モデルとして，暗号方式では選択暗号文攻撃に対する識別不可能性（IND-CCA），ディジタル署名では選択平文攻撃に対する存在的偽造不可能性（EUF-CMA）が用いられる．また，暗号方式の効率性の評価基準としては，公開鍵・暗号文・署名などのサイズ，鍵生成・公開鍵・秘密鍵を利用した演算スピード，復号の失敗確率などが用いられる．一方，実社会で利用を想定して，サイドチャネル攻撃・完全前方秘匿性・乱数再利用攻撃などに対する安全性評価もオプションとして考察される．更に，規格化された暗号が現在利用されている標準的な暗号規格に簡単に置き換えることが可能な（Drop-in-replacement）方式が望まれている．NIST PQC標準化プロジェクトに提案する場合は，以上の安全性及び効率性を自己評価したデータを含む必要があった．

　NISTによるPQC標準化プロジェクトの公募は2017年11月に締め切られ，公募条件を満たした方式は69件となった（表2）．そのうち，格子暗号25件，符号暗号18件，多変数多項式暗号10件，ハッシュ関数署名2件，同種写像暗号1件であった．全ての提案暗号は，NIST PQC標準化プロジェクトのホームページで公開されている．提案暗号を機能別に分類すると，鍵交換を含む暗号化方式は49件，ディジタル署名方式は20件となった．応募は世界中の25か国からあり，国別では北米とヨーロッパからの応募が多く，アジアからは日本，韓国，中国，台湾，シンガポール，オーストラリアから提案された．提案者は合計で278人に及び，そのうち67人は2件以上の方式を応募していた．日本からの提案は，KDDI総合研究所，東芝研究開発センター，情報通信研究機構，そして筆者の東京大学からのグループとなった．

　NIST PQC標準化プロジェクトでは，公開されたメーリングリストが準備されており，2018年12月までに600件以上のメールが投稿されるなど，提案方式の安全性などに関して多く活発な議論が交わされた．2019年1月にPQC標準化プロジェクトの第2ラウンドへ進む26方式が発表され，2020年7月には第3ラウンドの方式が選出された（図3）．第3ラウンドには，最終候補（Finalists）として7方式，代替方式（Alternate Candidates）として8方式が選出された．最終候補において，格子暗号が暗号化3方式及びディジタル署名2方式と主要な候補となった．その他の最終候補として符号暗号・多変数多項式暗号が選出され，代替方式として同種写像暗号・ハッシュ関数署名・一方向関数ベースの方式が選ばれた．NISTは格子暗号だけを標準化方式として選出するのではなく，安全性や性能の特性を考慮して他の基本問題を基にした方式も標準化する予定としている．

　2022年7月に最初の標準化方式が発表され，暗号化・鍵交換方式は格子暗号のCRYSTALS-Kyber，ディジタル署名は格子暗号のCRYSTALS-DilithiumとFALCON，そしてハッシュ関数署名のSPHINCS+が選定された（図4上側）．第3ラウンドの格子暗号の暗号化3方式から，演算が効率的であり安全性評価が十分に議論された点からCRYPTALS-Kyberが標準化方式となった．ディジタル署名では格子暗号から2方式が同時に選ばれたが，CRYSTALS-Dilithiumの署名長が比較的大きいため，短い署名長を必要とするシステムではFALCONが利用できる．また，ハッシュ関数署名SPHINCS+は高い安全性を実現する方式だが，署名長が大きい点や署名生成の回数に上限があるため，ソフトウェア配布など限定的用途を想定している．

　同時に，第4ラウンドの方式も発表され，符号暗号の3方式BIKE，HQC，Classic McEliece，同種写像暗号のSIKEが選出された．この符号暗号の3方式から暗号化の標準方式が選出される予定である（図4下側）．SIKEに関しては2022年8月に高次元多様体の構造を利用した多項式時間の解読法が提案された．一方，ディジタル署名は再公募されることになり，署名長が短く署名検証が高速な方式を募集していたが，2023年7月に公募条件を満たした40方式が公開されている．3ラウンドまでの情報は報告書NIST.IR.8413-upd1（https://doi.org/10.6028/NIST.IR.8413-upd1）に詳しい情報がある．

　最後に，2022年7月に選出された方式は，パブリックコメントを受け付けた後に2024年にNIST PQC標準方式（ML-KEM，ML-DSA，SLH-DSA）として規格化される予定である．現在利用される暗号システムの移行措置として，2030年まではSP 800-56，FIPS PUB 186-4で規定されている古典的安全性で128, 192, 256ビットの安全性強度を持つRSA暗号・だ円曲線暗号も利用可能としている（表3）．しかし，2031年以降に耐量子計算機暗号に移行するための準備期間は限られており，現在普及しているRSA暗号・だ円曲線暗号と耐量子計算機暗号をハイブリッドで利用することも検討されている．

4．お　わ　り　に

　本稿では，量子計算機の時代でも安全に利用可能となる耐量子計算機暗号の最新動向に関して解説した．特に，耐量子計算機暗号の代表的な方式を説明し，米国標準技術研究所NISTによるPQC標準化プロジェクトの概要を紹介した．2022年7月に格子暗号3方式とハッシュ関数署名1方式がNIST PQC標準暗号として選出され，追加の方式も第4ラウンド及び再公募として標準化活動が続いている．今後は，標準化される耐量子計算機暗号への移行に際して生じる問題に対応することが課題となる．

文　　　　　献

（2023年5月31日受付　2023年6月19日最終受付）