耐量子コンピュータ暗号の概要
これは
耐量子コンピュータ暗号について、その概要を大雑把にまとめたものです。
初心者向けの内容なのであまり深い内容は期待しないでください。
もし間違ったことを書いていた場合、ご指摘頂ければ幸いです。
背景
今日のインターネットでは、データの安全性・確実性を証明するためだったり、データの内容を第三者に見られないように暗号化するための公開鍵暗号技術として、RSA暗号や楕円曲線暗号などが広く使われています。
なぜ"安全"と言えるのか
RSA暗号や楕円曲線暗号などを使用して、なぜ安全と言えるのでしょうか。
たとえばRSA暗号は、簡単に言えば素因数分解の難しさを安全性の根拠にしています。（素因数分解問題）
素因数分解なんて別に簡単やろ、と思うかもしれません。
例えば6だったら、3*2とすぐに分かります。しかしこれはあくまで小さい数字だからで、素因数分解の対象となる数が大きくなればなるほど難しくなります。
例えば、ある暗号を最も効率の良い解読アルゴリズムで解読した時の計算量が2^kだった場合、その暗号の安全性はkビットとなります。
このような時間計算量が、2^kのような指数関数で表されるものではなく、多項式で表せられる場合、その計算時間を多項式時間と言います。
一般に、RSA暗号を多項式時間で解読するアルゴリズムは存在しないと言われています。が、証明（多項式時間で解くことができない、もしくは解くことができるという証明）はされていません。関連ワードとしてP≠NP予想というのがあるのですが、気になる方は調べてみてください。
と、少し脱線しましたが、RSA暗号やその他一般に使われる暗号は、計算量に着目して”解読するには膨大な計算が必要である”という仮定の元に安全と言われています。
量子コンピュータ
ここで量子コンピュータの登場です。
量子コンピュータは、これまでのような古典力学ではなく、量子力学を動作の原理としたコンピュータです。
量子コンピュータは今までのコンピュータと動作原理からして違うので、今までのコンピュータではできない、量子コンピュータで解くための量子アルゴリズムというのが存在します。
Shorのアルゴリズム
1994年に、アメリカの数学者Peter Shorの論文で「Shorのアルゴリズム」と呼ばれる量子アルゴリズムが発表されました。
このShorのアルゴリズムはなんと、RSA暗号や楕円曲線暗号の安全性の根拠になっている、素因数分解問題や離散対数問題を多項式時間で解くことができるという量子アルゴリズムです。
つまり、今まで安全と言われてきた暗号技術は、量子コンピュータを前にすると安全とは言えなくなるということです。
幸いにも(?)、Shorのアルゴリズムで現実的な時間で素因数分解問題や離散対数問題を解こうとするには、より大規模な量子コンピュータを作らないといけませんが、今の所その実現はまだまだ遠そうです。
耐量子コンピュータ暗号
RSA暗号や楕円曲線暗号などが簡単に解読されてしまうような量子コンピュータが実現される前に、量子コンピュータでも解読するのに時間がかかるような暗号というのを作らないといけません。
このような、量子コンピュータでも現実的な時間では解くことができないような（言い換えれば、量子コンピュータに対してでも安全な）暗号のことを耐量子コンピュータ暗号、または耐量子計算機暗号と言います。
耐量子コンピュータ暗号の候補となっている暗号はいくつかあり、格子暗号・多変数多項式暗号・同種写像暗号などが挙げられますが、ここでは格子暗号について触れてみます。
格子暗号
格子暗号と言ってもいくつか種類がありますが、一般に格子暗号とは、格子の性質に基づいた暗号の総称を指します。それらの暗号は、格子に関連した解くのが難しい問題を安全性の根拠としており、例として最短ベクトル問題や最近ベクトル問題などがあります。
例：最近ベクトル問題
ある高次元なベクトル空間において、ある点から最も近い格子点を求める問題を最近ベクトル問題といいます。
対象となるベクトル空間の次元が十分に大きければ、最近ベクトル問題を多項式時間で解くアルゴリズムは存在しない（これは量子コンピュータでも）と今のところは言われています。
また、最近ベクトル問題を安全性の根拠に活用した暗号をGGH系格子暗号と言います。
色々な格子暗号
最短ベクトル問題というのを応用したNTRU系格子暗号や、Learning with Errors問題というのを応用したLWE系格子暗号などがあります。
格子暗号の概要については、日本銀行金融研究所の以下の資料がとても参考になります。
量子コンピュータの解読に耐えうる暗号アルゴリズム「格子暗号」の最新動向
無断転載禁止の資料なのでその内容についてはここでは触れませんが、かなり分かりやすいです。
おわり
耐量子計算機暗号についてよく網羅された、
縫田光司（2020）『耐量子計算機暗号』森北出版
が普遍的な知識を学ぶのにとても良いです。というより、今のところ日本語の書籍で耐量子計算機暗号の全体像を体系的に学べるものはこれしかありません。
Discussion