はじめに
Post-quantum（耐量子計算機暗号;PQC）の話が最近盛り上がってきているので、まとめてみようと思います。
Who am i ?
しがないエンジニアです。
なぜPQCの話が盛り上がってきているのか？
近年、量子計算機の開発スピードが上がってきており、60q-bitを超えるくらいまでスケールしてきています。2030年を超えるあたりに現実的に既存の公開鍵暗号の脅威となるShorのアルゴリズムが解けるくらいの量子計算機（CRQC）ができるのでは？という推測があり、これの準備段階として2020年あたりから盛り上がってきているのが現状です。
念の為、誤解のないように記載するとここで述べている計算機はアニーリング型ではなくゲート型と呼ばれる計算機のことを指します。
CRQCの影響がクリティカルなのはどこなのか？
量子アルゴリズムにはGroverのアルゴリズムやShorのアルゴリズム等が有名ですが、Shorのアルゴリズムは多項式時間で素因数分解や離散対数問題を解くアルゴリズムのため、既存のRSAや楕円曲線暗号の安全性の仮定が崩れてしまうという問題があります。すなわち「素因数分解や離散対数問題が効率的に解けない限り、それに基づくRSAや楕円曲線暗号も安全」ということです。ただし、ShorのアルゴリズムはCRQCで動作させた場合、多項式時間アルゴリズムで解けるということが知られていたため、現実的なCRQCが開発されない限り、実際に多項式時間で素因数分解や離散対数問題が解けることはないだろうと議論されてきました。近年ゲート型の量子計算機の開発が進んでいるため、それに合わせて次世代の暗号も考えていかないといけないね、ということで議論が進んでいるというわけです。Shorのアルゴリズムが論文で発表されたのは、1994年頃らしいので30年前から議論自体はされているということですね。
量子計算機の開発動向
量子計算機にも色々種類があるようなのですが、日本で有名なものは超伝導状態を使って量子状態を人工的に作り出す方法です。
ただ、現実的に使えるCRQCには少なくとも1000q-bitくらいは必要だよねという声もあり、まだまだ暗号解読に使えるようなレベルには至っていないようです。こちらの動向もウォッチしていきたいところですね。
他にも色々量子状態を作り出す方法が研究されているようです。
日本総合研究所の方がまとめてくださっています。わかりやすいです。
PQCの動向
PQCの動向ですがNISTの標準化が進んできており、FIPSもDRAFTの状態です。NISTの標準化を待つばかりですね。
IETFでも議論が進んでいるようです。
日本銀行の宇根さんがまとめてくださっている資料が大変わかりやすいです。
日本国内の状況
総務省で最近資料がアップロードされていました。
CRYPTRECでも資料がアップロードされています。
最後に
耐量子暗号が注目を浴びている中で、クリプトアジリティについても議論されるようになってきました。NISTの標準化を首を長くして待とうと思います。