取り上げた公開鍵暗号について

今回の記事では、素因数分解と楕円曲線暗号の困難性を破ることが出来るという意味で、公開鍵暗号を破るという言葉を使っています。SIDH等の耐量子鍵プロトコルに関しては例外という扱いをさせていただきます。あらかじめご承知おきください。

量子コンピュータは何が出来るのか

量子コンピュータとは、誤解を恐れずに言えば、いろいろな選択肢を一度に試すことが出来るコンピュータです。「波」の性質を持つ物質を用いて、それぞれの入力をすべて重ね合わせた状態で演算をし、最終的に得られる状態を観測することによって、高確率で正しい答えを求めることが出来ます。しかし、あらゆる計算が高速化できるわけではなく、因数分解や組み合わせ最適化問題、検索等の量子アルゴリズムが発見されている問題のみが高速化可能です。また、「高速化」とは言っても、これは計算に要するステップがより少なくなることを指し、実時間で高速に演算ができるかどうかは、各ハードウェアの性能に依存してきます。例えば、現在最も量子ゲート方式で量子ビット数が多い（≒性能が高い）IBMの量子コンピュータは53量子ビットの演算が可能であり、2⁵³個の状態を重ね合わせて演算が可能です。

POINT

1. 量子コンピュータは多数の組み合わせを一度に試せる。
2. 高速化とは、ステップ数が減ることを指し、必ずしも実際「速い」とは限らない。

なぜ公開鍵暗号は（現在）安全なのか

では、なぜ量子コンピュータは公開鍵暗号を破れると考えられているのでしょうか。

そのためにはまず、なぜ公開鍵暗号方式が安全であると考えられているか知る必要があります。その根拠となっているのは公開鍵暗号の根底に存在する数学的難問を、今の人類の技術で解くことが出来ないという事実です。つまり、現在利用されている公開鍵暗号方式は情報量的に安全なわけではなく、攻撃者のリソースが有限であり、現実的な時間内で解読が不可能である問題だという仮定に基づいているということです。これは、根底にある数学的問題を解ける技術が開発された場合、安全性を担保する理由がなくなることを意味します。この「安全性を担保する理由がなくなった」状態を、暗号が「破られた」と言います。

次に、公開鍵暗号方式の根底に存在する数学的難問を考えます。まず、RSA暗号に関しては、素因数分解の困難性に関する問題が根拠とされています。巨大な数を素因数分解することには、厖大な計算が必要となるため、人類にRSA暗号を現実的な時間で解くことはできないと考えられます。例えば、768ビットのRSA暗号は2009年に解読されましたが、その次のステージとされている896ビットのRSA暗号はいまだに解かれていません。よって、少なくとも現在使われている1024ビット以上のRSA暗号を解くことは難しいでしょう。次に、ElGamal暗号(あるいはECDHなどの楕円曲線暗号)は、有限体上で定義される楕円曲線上の離散対数問題の困難性を根拠としています。こちらも、2009年にECCという暗号方式の112ビットの法を持つ暗号が解読されました。

　POINT

1. 公開鍵暗号は数学的難問を根拠に、安全性を担保している。
2. 現在のコンピュータ性能では、現実的な時間で十分な鍵の長さを持つ公開鍵暗号を解読することはできない。
3. 数学的難問が解かれたなら、暗号は破られる。

古典コンピュータでは公開鍵暗号を破ることは難しいのか

結論から言うと、古典コンピュータで公開鍵暗号を破ることは非常に難しいと言えます。なぜならば、コンピュータの性能の向上よりも、暗号を難しくすることの方が容易だからです。

RSA暗号は1977年に公開されましたが、それから10年以上経った1991年に100ビットのRSA暗号が解読されました。しかし、そこから2009年の768ビットRSAに至るまでは数年間隔で解読されていましたが、それ以降RSA暗号の解読実績はありません。それに対して、現在使われているRSA暗号の鍵長は1024~4096ビットです。このことから、以前のペースで解読を続けたとしても、RSA暗号を破ることは難しいと言えそうです。

　POINT

1. 古典コンピュータの性能向上よりも暗号の強化の方が速い。

なぜ量子コンピュータは公開鍵暗号を破れるのか

それでは、本題の量子コンピュータが公開鍵暗号を破ることが出来る理由について、説明していきます。実は、素因数分解に関しても、楕円曲線上の離散対数問題に関しても、まったく同じ量子アルゴリズムを利用することが出来ます。それはShorのアルゴリズムというもので、量子コンピュータがDFT（離散フーリエ変換）を高速に行う事が出来ることを利用したアルゴリズムです。

どのくらい高速に行うことが出来るかというと、データ数N=2ⁿとしたときに、古典コンピュータの最速アルゴリズムFFTがO(n2ⁿ)程度の計算量ですが、量子コンピュータの最速アルゴリズムQFTがO(n²)程度の計算量です。試しにn=100を代入してみると、FFTが12,676,506,002,282,29,401,496,703,205,376回程度の計算をしなければならないのに対し、QFTでは1,000回程度の計算で済みます。数が大きすぎてよくわからないと思いますが、圧倒的に速いということをわかっていただければ大丈夫です。

このとても速い量子離散フーリエ変換を用いて、量子位数発見という計算を行うのが、Shorのアルゴリズムの最も重要な部分となります。

素因数分解の場合、aをランダムな数、Nを合成数として、f(x)= a^x mod Nという関数の位数がその周期と等しいことを利用して、周期rを特定することで、位数rを発見します。位数が分かったら、その位数から因数を特定することが出来ます。

楕円曲線上の離散対数問題に関しては、g, pをそれぞれ生成元, pを有限体の位数として、f(a, b)=g^a-xb mod pという関数の周期はxに依存していることを利用し、QFTを行う事でxを特定することが出来ます。

Shorのアルゴリズムは確率的なアルゴリズムですので、毎回きちんと因数分解できるわけではないですが、前述したように古典的アルゴリズムよりも相当に高速なので、解を得るまでに何度か試行したところで、多少の誤差とみることが出来ます。（O記法では定数倍が無視されるイメージでいいと思います。）

ここまで説明したところで、そこまで高速化したところで、暗号の強化速度に間に合わなきゃ仕方がないじゃないか。と思う方もいらっしゃると思います。しかし、量子コンピュータ（量子ゲート方式の場合）は、1量子ビットの増加によって、2倍の演算能力を得ることが出来ます。そのため、電源や廃熱等でこれ以上の演算能力を得ることが難しい古典コンピュータと比べると、比較的演算能力の強化が容易であることから、これらの暗号が強化されるよりも早く量子コンピュータが発達するのではないかと期待されています。

POINT

1. 2つの問題は、どちらもShorのアルゴリズムというものを利用して解くことが出来る。
2. 量子コンピュータは離散フーリエ変換が得意で、Shorのアルゴリズムはそれを利用している。
3. Shorのアルゴリズムの肝は、量子位数発見である。
4. 量子コンピュータの開発速度の方が暗号の強化よりも速いと期待されている。

今すぐ量子コンピュータは公開鍵暗号を破ることが出来るのか

結論から言うと、今すぐに量子コンピュータが公開鍵暗号を破ることはできません。その理由として、現在利用可能な量子コンピュータの性能では、RSA暗号やElGamal暗号を解くことが非常に困難であるからです。具体的には、256ビットの法を持つ楕円曲線暗号を破るためには2330量子ビット、2048ビットのRSA暗号を破るためには4098量子ビットの量子コンピュータが必要になります[1]。よって、しばらくは公開鍵暗号を破ることのできる量子コンピュータが実用化されることはない、というのが私なりの解釈です。一方で、新たな計算手法によるブレイクスルーが起きる可能性が全くないとも言い切れず、今後も注目していきたい領域の一つです。

参考文献等

1. 楕円曲線ディフィー・ヘルマン鍵共有 - Wikipedia [link]

2. 量子アルゴリズムの基本：Shorのアルゴリズムの確認（その１）[link]

3. 今井秀樹, “情報セキュリティと想定外”, IEICE Fundamental Review Vol.5 No.3 p.199
4. Elmgamal暗号 – Wikipedia [link]
5. RSA暗号#RSA暗号解読コンテスト – Wikipedia [link]

[1] Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin (2017). “Quantum resource estimates for computing elliptic curve discrete logarithms”. arXiv:1706.06752 [quant-ph]