こんにちは、データ＆セキュリティ研究所の伊豆です。
データ＆セキュリティ研究所では、量子計算機がセキュリティに与える影響を分析しています。 2022 年に量子計算による最適化手法を用いた新しい素因数分解法が発表され、注目を集めています。 われわれはこの手法の効果を調査するためにさまざまな実験を行ったので、その結果を紹介します。 この結果は情報処理学会のコンピュータセキュリティ研究会でも発表予定です。
論文情報
- 研究会名：情報処理学会 コンピュータセキュリティ(CSEC)研究会
- 開催日：2023年5月11日(木)～12日(金)
- 開催場所：高知市 (およびオンライン)
- 論文タイトル：格子と最適化手法を用いた素因数分解法の実験報告
- 著者：山口 純平 (富士通), 伊豆 哲也 (富士通), 國廣 昇 (筑波大学)
背景
SSL/TLS などのインターネット通信で使用されているRSA暗号やRSA署名は、 巨大な合成数の素因数分解が難しいという性質を利用して安全性を保証しています。 これまでの素因数分解の世界記録は829ビット合成数の素因数分解であるため、 インターネット通信では2048ビット以上の合成数を利用することで、 素因数分解による解読攻撃を避けています。
しかし理想的な量子計算機が実現した場合、 Shorが開発した素因数分解法 (Shor アルゴリズム) を用いることで、 従来よりもごく短時間で2048ビット合成数が素因数分解できることが知られています。 ただし Shor アルゴリズムは数千オーダーの量子ビットを必要とし、 量子ビットの処理エラーも許容しないため、 Shor アルゴリズムによる素因数分解が実現するまでには相当な時間が必要と考えられています。
【参考】富士通, 量子シミュレータを活用したRSA暗号の安全性評価に成功 (2023年1月23日)
最適化手法を利用した素因数分解法
2022 年 12 月に Yan 等は最適化手法を利用した素因数分解法を発表しました。 具体的には以下のような特徴を備えていました。
- 素因数分解をハミルトニアンと呼ばれる関数の最小値を求める問題(最適化問題)に変換する
- QAOA (Quantum Approximate Optimization Algorithm) と呼ばれる量子計算を用いてハミルトニアンの最小値を求める
- 必要な量子ビット数は合成数のビット長の劣線型 (sublinear) になる
さらに超伝導方式の量子計算機を用いた実験において、 48ビット合成数を素因数分解するのに10量子ビットで処理できたことが報告されています。 同じ合成数を素因数分解するのに Shor アルゴリズムは 98 量子ビット以上が必要なることから この素因数分解法は大きく注目を集めました。
【参考】最適化手法を利用した素因数分解法の解説 qiita.com
数値実験の内容
最適化手法を利用した素因数分解法は「関係式」というデータを収集する際に使用します。 例えば48ビット合成数を素因数分解するには200個以上の関係式が必要なのですが、 最適化手法を利用した素因数分解法はこのうちの数個しか求められず、 素因数分解全体の処理の効率化にはあまり寄与できないという課題がありました。
そこでわれわれは提案方式を拡張し、素因数分解するのに必要な全ての関係式を
最適化手法によって求められるアルゴリズムを開発しました。
この拡張方式を用いて数値実験を行ったところ、
11ビットから55ビットまでの45個の合成数の素因数分解に成功しました。
最大の計算例は55ビット合成数 で、
という素因数分解結果を得ることができました.
これは提案方式の実験よりも大きな合成数となっています。
ただし拡張方式を用いて素因数分解した場合、 提案方式よりもたくさんの最適化問題と多くの量子ビットが必要であることもわかりました。 したがって。提案方式や拡張方式が従来方式よりも理論的、 あるいは現実的に効率的であるかはさらなる解析が必要です。 詳細な実験データについては、是非、論文をご覧下さい。
なお、われわれの実験では、最適化問題のソルバーとして富士通が開発した Digital Annealer を使用しました。 実験では全ての合成数の素因数分解に成功していることから、 今回の実験規模であれば、最適化手法を利用した素因数分解法における QAOA の利用は必須ではないことがわかりました。
参考資料
- Yan et al.: Factoring integers with sublinear resources on a superconducting quantum processor arxiv.org
- Yamaguchi et al.: Estimation of Shor's Circuit for 2048-bit Integers based on Quantum Simulator eprint.iacr.org
