量子コンピュータ実機を用いた離散対数問題の求解実験に成功
2020年12月9日
国立研究開発法人情報通信研究機構(NICT)
ポイント
■ IBM社の超電導量子コンピュータを用いた離散対数問題の求解実験に成功
■ 離散対数問題の多様性のある特性を生かした量子コンピュータ向けプログラミング
■ 現在の暗号への脅威の将来予測、耐量子計算機暗号への移行の第一歩に向けて
国立研究開発法人情報通信研究機構(NICT)、学校法人慶應義塾(慶應大学)、株式会社三菱UFJフィナンシャル・グループ(MUFG)、株式会社みずほフィナンシャルグループ(MHFG)は、IBM Q Hub at Keio Universityのある慶應義塾大学量子コンピューティングセンター(KQCC)において、量子コンピュータ時代における暗号の安全性確保のための第一歩として、クラウドからアクセス可能な量子コンピュータであるIBM Quantumを使用した小規模離散対数問題の求解実験に成功しました。
離散対数問題は、現代の情報社会を支える暗号技術の安全性の根拠の一つとなっている極めて重要な問題であり、量子コンピュータ実機で解くことのできる離散対数問題の規模を知ることが重要な課題です。また、離散対数問題は、実験可能な量子プログラムの選択の幅が広く、暗号への脅威の将来予測のための量子コンピュータ実験に適しているのではないかという事前検討を踏まえ、実験を行いました。
本成果は、今後、量子コンピュータによる現代暗号の危殆化時期の予測検討に利用される予定です。
背景
現代の情報社会を支える暗号技術の安全性を保障する数学的な問題の一つに、離散対数問題があります。離散対数問題は、一定の性能を有する量子コンピュータを用いることで、高速に解かれてしまうことが理論的には証明されているため、量子コンピュータの性能向上により、暗号技術が危殆化することが懸念されています。対策として、一定の性能を持つ量子コンピュータの出現後も暗号の安全性を担保できると期待されている耐量子計算機暗号への移行に向けた検討が、米国国立標準技術研究所(NIST)を中心に世界的に進められています。その移行が必要となる時期を予測するため、現在利用可能な量子コンピュータを用いて、どの程度の規模の離散対数問題が解けてしまうのかを把握することが重要です。
今回の成果
今回、NICTら4者のグループは、量子コンピュータ時代における暗号の安全性確保に向け、離散対数問題によって安全性が保障される暗号方式の危殆化時期評価に関する活動を開始しました。その活動の第一歩として、ショアのアルゴリズムを離散対数問題用にプログラミングし、量子コンピュータ実機による離散対数問題の求解実験に世界で初めて成功しました。
【画像:https://kyodonewsprwire.jp/img/202012098314-O4-34bMHc9u】
今回の実験は、NICTが実験用の量子プログラムを設計した後、慶應大学、MUFG、MHFGにより超電導量子コンピュータIBM Quantumに合わせた効率化を行い、IBM Quantumの実デバイス上で実験を行いました。その出力結果の検討を4者で行ったところ、問題が解けているとの結論に至りました。
今回の成果は、まだ初歩的段階であるため、現在使われている暗号技術の安全性に脅威を与えることはありませんが、暗号技術の危殆化時期を予測する上で重要かつ貴重な一歩になったと考えています。
今回の実験と結果の概要
ショアのアルゴリズムは、素因数分解問題や離散対数問題を含む様々な問題に適用可能なため、それらの問題を安全性の根拠とする暗号技術への脅威となる可能性があることから、様々な研究が行われています。特に、RSA暗号の安全性の根拠として利用されている素因数分解問題については、量子コンピュータを用いた様々な実験が行われてきました。一方、離散対数問題については、実験に成功したという報告はありませんでした。
暗号がいつ解かれてしまうのかを予測するために、その暗号の安全性の根拠となる問題がどの程度解かれてしまうのかを調べることは重要です。今回、ショアのアルゴリズムの暗号への影響を調査するため、両問題の実験について検討を行いました。その結果、離散対数問題の小規模なサンプル問題であれば、プログラミングを工夫することで、求解実験が成功する可能性があることが分かりました。
今回の実験のため、離散対数問題のいくつかのサンプル問題に対して量子コンピュータ向けのプログラミングを行い、そのプログラムの規模がどの程度までであれば、量子コンピュータ実機によって解くことが可能なのかを調べました。図2は、実験を行ったプログラムを規模の順に並べ、量子コンピュータ実機で実験を行った結果をまとめたものです。今回実験を行った中で最も小さい規模の量子プログラム①の実行では、量子コンピュータ実機が十分に良い結果を出力しましたが、より大きな規模のプログラム②及び③では良い結果が出力されませんでした。
そのため、現在の技術により解くことのできる量子プログラムの規模は、図中①と②の間であるという結論を得ました。これは、離散対数問題を量子コンピュータ実機で解いた初めての成果となります。また、プログラム②の出力を検証したところ、プログラムの規模をより小さく改良することができれば、解ける可能性が残されているという結論に至りました。
【画像:https://kyodonewsprwire.jp/img/202012098314-O2-lG2pR8Gm】
今後の展望
今後も、量子コンピュータの性能の向上に合わせて定期的な実験報告を行うことで、現在用いられている暗号技術の危殆化時期をできる限り正確に見積もり、暗号技術の安全性評価の活動へとつなげていきます。
本研究成果について、2020年12月10日(木)、11日(金)にオンライン開催される第43回量子情報技術研究会(QIT43)にて発表する予定です。
発表情報
名称: 第43回量子情報技術研究会(QIT43)
日時: 2020年12月11日(金)
タイトル: 超電導量子回路を用いた離散対数問題の求解実験
ノンスタ井上、新幹線内で緊急事態に遭遇「お客様の中に…」アナウンス「初めて聞いた」
大谷翔平24号先頭打者弾!シーズン48本ペース、毎年好調の「6月」3度目の月間2桁本塁打
大谷翔平の24号にオリファンが吉兆の予感 チーム本塁打数に並ばれるも「大谷が打ったから…」
7/1発売【カルディ】夏のコーヒーバッグが元取れ確実!3種のお得な中身&近年とのバッグ比較、美味しい淹れ方もご紹介
いきなり号砲!大谷翔平が第1打席でいきなり24号 追い込まれてからのカーブに泳ぐも衝撃弾
遠野なぎこ、誹謗中傷やまずSNSコメント欄閉鎖「悔しくて、申し訳なくて…」
「芸能界で一番カッコいい」超大物俳優が千鳥・大悟に「ビッグになったね」ノブは大興奮
山口・宇部市バス 速度超過50キロ 走行中たばこ 運転士2人処分
大谷翔平、69年ぶり球団タイの9試合連続打点も記録 24号先頭打者弾でカンパネラに並ぶ
交際女性にも暴行疑い 3歳を洗濯機に入れけがさせた男性を再逮捕
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
都知事選掲示板にヌードポスター ひろゆき氏「世も末」 SNSで批判噴出
イケメンだから許される!堀北真希と山本耕史の「馴れ初め」が映画化希望するレベル
「ひまそらあかね」が突如トレンド入り!都知事選に出馬した暇空茜って一体どんな人?本物なの?
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
都知事選のほぼ全裸ポスター、イメージガールが謝罪 自身が携わる商品PR活動を辞退を発表
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
バキ童こと春とヒコーキのぐんぴぃが有吉の壁に登場!「笑いが止まらん」「地上波ゴールデンは草」
有権者「ばかにしている」 都知事選の掲示板に大量の同じポスター
何があった!?「エアコン」が想定外の壊れ具合!投稿者に話を聞いた
玉置浩二の妻、青田典子(53)の現在がとんでもない事になっていると話題に
イケメンだから許される!堀北真希と山本耕史の「馴れ初め」が映画化希望するレベル
都知事選掲示板にヌードポスター ひろゆき氏「世も末」 SNSで批判噴出
ガーシーが綾野剛のLINE公開でネット騒然「ショック」「すごいエンタメ」
ユーチューバーもこう氏、元彼女・成海瑠奈について赤裸々告白
柏原崇(45)現在を調べてみた結果、相変わらずかっこよすぎた!
「愛が生まれた日」藤谷美和子(56)の現在がヤバい!?徘徊生活を送っていた過去も明らかに。
松本人志飲み会参加セクシー女優「警察に相談しに行きました」報告「さすがにこれは酷すぎる」
【ネタバレ?】史実で見るキングダムの今後の展開まとめ〜中華統一までの全体像
ノンスタ井上、新幹線内で緊急事態に遭遇「お客様の中に…」アナウンス「初めて聞いた」
大谷翔平24号先頭打者弾!シーズン48本ペース、毎年好調の「6月」3度目の月間2桁本塁打
大谷翔平の24号にオリファンが吉兆の予感 チーム本塁打数に並ばれるも「大谷が打ったから…」
いきなり号砲!大谷翔平が第1打席でいきなり24号 追い込まれてからのカーブに泳ぐも衝撃弾
7/1発売【カルディ】夏のコーヒーバッグが元取れ確実!3種のお得な中身&近年とのバッグ比較、美味しい淹れ方もご紹介
遠野なぎこ、誹謗中傷やまずSNSコメント欄閉鎖「悔しくて、申し訳なくて…」
「芸能界で一番カッコいい」超大物俳優が千鳥・大悟に「ビッグになったね」ノブは大興奮
山口・宇部市バス 速度超過50キロ 走行中たばこ 運転士2人処分
大谷翔平、69年ぶり球団タイの9試合連続打点も記録 24号先頭打者弾でカンパネラに並ぶ
航空券が安くなるタイミングとは 国際線・国内線何日前が安い?を解説