Presentation | 2023-07-24 Implementation of Shor's algorithm for the discrete logarithm problem and experiments using the quantum computer simulator Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu, Noboru Kunihiro, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | discrete logarithm problem / quantum computation / quantum circuit simulation / Shor's algorithm / safe prime / DSA |
Paper # | ISEC2023-32,SITE2023-26,BioX2023-35,HWS2023-32,ICSS2023-29,EMM2023-32 |
Date of Issue | 2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
Conference Information | |
Committee | EMM / BioX / ISEC / SITE / ICSS / HWS / IPSJ-CSEC / IPSJ-SPT |
---|---|
Conference Date | 2023/7/24(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Hokkaido Jichiro Kaikan |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Michiharu Niimi(Kyushu Inst. of Tech.) / hironobu Takano(Toyama Prefectural Univ.) / Goichiro Hanaoka(AIST) / Takushi Otani(Kibi International Univ.) / Daisuke Inoue(NICT) / Daisuke Suzuki(Mitsubishi Electric) |
Vice Chair | Kotaro Sonoda(Nagasaki Univ.) / Hyunho Kang(NIT, Tokyo) / Norihiro Okui(KDDI Research) / Emiko Sano(Kubota) / Junji Shikata(Yokohama National Univ.) / Shinsaku Kiyomoto(KDDI Research) / Soichiro Morishita(Cyber Agent) / Takeo Tatsumi(Open Univ. of Japan) / Akira Yamada(Kobe Univ.) / Toshihiro Yamauchi(Okayama Univ.) / Yuichi Hayashi(NAIST) / Toru Akishita(Sony Semiconductor Solutions) |
Secretary | Kotaro Sonoda(Hiroshima City Univ.) / Hyunho Kang(Osaka Inst. of Tech.) / Norihiro Okui(NEC) / Emiko Sano(Gunma Univ) / Junji Shikata(AIST) / Shinsaku Kiyomoto(Toshiba) / Soichiro Morishita(NRI-Secure) / Takeo Tatsumi(Fukuoka Inst. of Tech.) / Akira Yamada(Mitsubishi Electric) / Toshihiro Yamauchi(Univ. of Electro-Comm.) / Yuichi Hayashi(Sony Semiconductor Solutions) / Toru Akishita(AIST) |
Assistant | Naofumi Aoki(Hokkaido Univ.) / Kazuaki Nakamura(Tokyo Univ. of Science) / Tomokazu Kawahara(Toshiba) / Shinichi Shirakawa(Yokohama National Univ.) / Hiroki Okada(KDDI Research) / Yusuke Kaneko(Japan Research Institute) / Yo Kanemoto(NTT) / Masaya Sato(Okayama Prefectural Univ.) |
Paper Information | |
Registration To | Technical Committee on Enriched MultiMedia / Technical Committee on Biometrics / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Technical Committee on Hardware Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Implementation of Shor's algorithm for the discrete logarithm problem and experiments using the quantum computer simulator |
Sub Title (in English) | |
Keyword(1) | discrete logarithm problem |
Keyword(2) | quantum computation |
Keyword(3) | quantum circuit simulation |
Keyword(4) | Shor's algorithm |
Keyword(5) | safe prime |
Keyword(6) | DSA |
1st Author's Name | Kaito Kishi |
1st Author's Affiliation | Fujitsu Research(Fujitsu Research) |
2nd Author's Name | Junpei Yamaguchi |
2nd Author's Affiliation | Fujitsu Research(Fujitsu Research) |
3rd Author's Name | Tetsuya Izu |
3rd Author's Affiliation | Fujitsu Research(Fujitsu Research) |
4th Author's Name | Noboru Kunihiro |
4th Author's Affiliation | Faculty of Engineering, Information and Systems, University of Tsukuba(Univ. of Tsukuba) |
Date | 2023-07-24 |
Paper # | ISEC2023-32,SITE2023-26,BioX2023-35,HWS2023-32,ICSS2023-29,EMM2023-32 |
Volume (vol) | vol.123 |
Number (no) | ISEC-129,SITE-130,BioX-131,HWS-132,ICSS-133,EMM-134 |
Page | pp.pp.119-126(ISEC), pp.119-126(SITE), pp.119-126(BioX), pp.119-126(HWS), pp.119-126(ICSS), pp.119-126(EMM), |
#Pages | 8 |
Date of Issue | 2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) |