情報通信研究機構(NICT)は12月9日、量子コンピュータ時代における暗号の安全性確保のための第一歩として、クラウドからアクセス可能な量子コンピュータであるIBM Quantumを使用した「離散対数問題」の求解実験を実施し、既存の量子コンピュータの性能でも小規模な離散対数問題であれば解けることを発表した。

同成果は、NICT、慶應義塾大学、三菱UFJフィナンシャル・グループ、みずほフィナンシャルグループの共同研究チームによるもの。詳細は、オンライン開催される第43回量子情報技術研究会において、2日目の12月11日に「超電導量子回路を用いた離散対数問題の求解実験」として発表される予定だ。

「離散対数問題」は、米国国立標準技術研究所(NIST)標準のデジタル署名方式をはじめとする重要な暗号技術の安全性を保障する、非常に重要な数学的問題だ。RSA暗号の安全性を保証する「素因数分解問題」と同様に、“解けてはならない”問題である。

離散対数問題も素因数分解問題も、既存のコンピュータ(古典コンピュータ)では、仮にスーパーコンピュータの性能であったとしても解けないことがわかっている。しかし、技術の進展とともにそれが揺らぎつつある。量子コンピュータが登場したからだ。

既存の量子コンピュータはまだ解答できる性能を有していないと考えられているが、今後、一定以上の性能を獲得した段階で「ショアのアルゴリズム」を実行すれば、離散対数問題も素因数分解問題も効率的に解けることが証明されている。つまり、「暗号技術の危殆化」が近づいてきているということである。

  • 量子コンピュータ

    暗号の危殆化時期の予測に関する今回の成果を表す鳥瞰図 (出所:NICT Webサイト)

なお、ショアのアルゴリズムとは、量子コンピュータが有する、入力された関数の周期(繰り返しパターンの間隔)を発見する能力を利用して問題を解くアルゴリズムのことである。

暗号技術の危殆化に対する備えとして、一定の性能を持つ量子コンピュータが出現しても安全性を担保できると期待されている耐量子計算機暗号への移行に向けた検討が、NISTを中心に世界的に進められている。そして、あとどのぐらいの猶予があるのか、移行が必要となる時期を予測するため、現在利用可能な量子コンピュータを用いて、どの程度の規模の離散対数問題や素因数分解問題が解けてしまうのかの把握が重要視されている。

そうした背景を受けて共同研究チームは、離散対数問題によって安全性が保障される暗号技術の危殆化時期評価に関する活動を開始した。その第一歩として、今回の研究では「ショアのアルゴリズム」を離散対数問題用にプログラミングし、量子コンピュータ実機による求解実験が実施されたのである。実験では、規模がどの程度までであれば量子コンピュータ実機によって解くことが可能なのか、規模の異なる3種類の離散対数問題のプログラムが用意された。なお、これまでのところ離散対数問題が解けたという報告はないという。

量子コンピュータを用いた実験結果としては、もっとも小さい規模の量子プログラムでは、十分に良い結果が出力されたという。また、その検討を4者によって行わったところ、問題が解けているという結論に至ったとした。

  • 量子コンピュータ

    離散対数問題を解く量子コンピュータプログラムの規模と実験結果。棒グラフ隣の数字は操作回数で、数が実行時に正しい出力を得ることが困難であることが示された (出所:NICT Webサイト)

ちなみに、離散対数問題が解けたとはいっても暗号技術の危殆化が訪れてしまったわけではない。解けたのはあくまでも小規模な問題であり、それが即座に現在使われている暗号技術の安全性に脅威を与えるものではないとしている。また、より規模の大きなプログラムの場合、良い結果は出力されなかったという。

そして今回の成果により、現在の技術により解くことのできる量子プログラムの規模が示されることとなった。また、良い結果が出力されなかった規模のプログラムについては、プログラムの規模をより小さく改良することができれば、解ける可能性が残されているという結論に至ったとしている。

今回の成果に対して共同研究チームは、暗号技術の危殆化時期を予測するうえで重要かつ貴重な一歩になったとしている。今後も、量子コンピュータの性能向上に合わせて定期的な実験報告を行うことで、現在用いられている暗号技術の危殆化時期をできる限り正確に見積もり、暗号技術の安全性評価の活動へとつなげていくとしている。