| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-07-24 18:20 離散対数問題に対するShorアルゴリズムの実装と量子計算機シミュレータを用いた実験 ○岸 海斗・山口純平・伊豆哲也（富士通研）・國廣 昇（筑波大）  ISEC2023-32 SITE2023-26 BioX2023-35 HWS2023-32 ICSS2023-29 EMM2023-32 |
|
| 抄録 | （和） | 暗号分野でよく用いられる素体上の離散対数問題は古典計算機では解くための多項式時間アルゴリズムが見つかっていない．一方，量子計算機による多項式時間アルゴリズムがShorにより与えられており，離散対数問題を解くのに必要なゲート数などのリソースを見積もることが求められている．しかし，素因数分解と比べて離散対数問題を解く量子シミュレーション結果は不足しており，その見積もりをするには不十分である．本研究では32量子ビットで可能な1860通りすべての離散対数問題を解く量子シミュレーションを行い，加算にQ-ADDを用いると標数が2048ビットのときは8194量子ビットと$1.04times 10^{15}$の量子ゲートが必要と推定できた．また，量子計算機が解くにあたって他のパターンと比べて難しいような離散対数問題の種類を発見した． |
| （英） | Classical polynomial-time algorithms for solving the discrete logarithm problem (DLP) over a prime field have not been found yet, and many cryptosystems are constructed based on them. However, a quantum polynomial-time algorithm for it was given by Shor. Previous quantum simulates to estimate resources for solving DLP are still lacking. In this study, we estimated that 8194 qubits and $1.04times 10^{15}$ quantum gates are required to solve DLP of a 2048 bits characteristic with Q-ADD by simulating quantum circuits solving 1860 patterns of DLP. We also found a type of DLP which are more difficult than other types of them to solve in quantum computers. |
|
| キーワード | （和） | 離散対数問題 / 量子計算 / 量子回路シミュレーション / Shorアルゴリズム / 安全素数 / DSA署名 / / |
| （英） | discrete logarithm problem / quantum computation / quantum circuit simulation / Shor's algorithm / safe prime / DSA / / | |
| 文献情報 | 信学技報, vol. 123, no. 129, ISEC2023-32, pp. 119-126, 2023年7月. | |
| 資料番号 | ISEC2023-32 | |
| 発行日 | 2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2023-32 SITE2023-26 BioX2023-35 HWS2023-32 ICSS2023-29 EMM2023-32 |
|
| 研究会情報 | |
| 研究会 | EMM BioX ISEC SITE ICSS HWS IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2023-07-24 - 2023-07-25 |
| 開催地（和） | 北海道自治労会館 |
| 開催地（英） | Hokkaido Jichiro Kaikan |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2023） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2023-07-EMM-BioX-ISEC-SITE-ICSS-HWS-CSEC-SPT |
| 本文の言語 | 日本語 |
| タイトル（和） | 離散対数問題に対するShorアルゴリズムの実装と量子計算機シミュレータを用いた実験 |
| サブタイトル（和） | |
| タイトル（英） | Implementation of Shor's algorithm for the discrete logarithm problem and experiments using the quantum computer simulator |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 離散対数問題 / discrete logarithm problem |
| キーワード(2)（和/英） | 量子計算 / quantum computation |
| キーワード(3)（和/英） | 量子回路シミュレーション / quantum circuit simulation |
| キーワード(4)（和/英） | Shorアルゴリズム / Shor's algorithm |
| キーワード(5)（和/英） | 安全素数 / safe prime |
| キーワード(6)（和/英） | DSA署名 / DSA |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岸 海斗 / Kaito Kishi / キシ カイト |
| 第1著者 所属（和/英） | 富士通株式会社富士通研究所 (略称： 富士通研) Fujitsu Research (略称： Fujitsu Research) |
| 第2著者 氏名（和/英/ヨミ） | 山口 純平 / Junpei Yamaguchi / ヤマグチ ジュンペイ |
| 第2著者 所属（和/英） | 富士通株式会社富士通研究所 (略称： 富士通研) Fujitsu Research (略称： Fujitsu Research) |
| 第3著者 氏名（和/英/ヨミ） | 伊豆 哲也 / Tetsuya Izu / イズ テツヤ |
| 第3著者 所属（和/英） | 富士通株式会社富士通研究所 (略称： 富士通研) Fujitsu Research (略称： Fujitsu Research) |
| 第4著者 氏名（和/英/ヨミ） | 國廣 昇 / Noboru Kunihiro / クニヒロ ノボル |
| 第4著者 所属（和/英） | 筑波大学システム情報系 (略称： 筑波大) Faculty of Engineering, Information and Systems, University of Tsukuba (略称： Univ. of Tsukuba) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-07-24 18:20:00 |
| 発表時間 | 20分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2023-32, SITE2023-26, BioX2023-35, HWS2023-32, ICSS2023-29, EMM2023-32 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.129(ISEC), no.130(SITE), no.131(BioX), no.132(HWS), no.133(ICSS), no.134(EMM) |
| ページ範囲 | pp.119-126 |
| ページ数 | 8 |
| 発行日 | 2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]