剰余逆元計算の新しい量子アルゴリズムと楕円曲線離散対数問題への応用

• Item type: SIG Technical Reports(1)
• 公開日: 2019-07-16
• タイトル: 剰余逆元計算の新しい量子アルゴリズムと楕円曲線離散対数問題への応用
• タイトル / 言語: en
• タイトル: New Quantum Algorithms for Modular Inverse and Their Application on the Elliptic Curve Discrete Logarithm Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 筑波大学システム情報系
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): University of Tsukuba
• 著者名: 鞍馬, 遼; 國廣, 昇
• 著者名(英): Ryo, Kurama; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 楕円曲線暗号は今日では様々な場面で利用されている．楕円曲線離散対数問題 (ECDLP) はその楕円曲線暗号の安全性を保証する重要な問題である．ECDLP は量子多項式時間で解くアルゴリズムが存在し，これに対する具体的な回路の提案も過去になされている．この量子回路において，剰余逆元計算は回路サイズに対するボトルネックとなる．今回我々は剰余逆元計算に対して剰余指数化タイプと反復剰余 2 倍タイプの 2 つのアルゴリズムを提案する．過去のアルゴリズムが抱えていた課題も新たな剰余逆元の定義を採用することで解決している．このアルゴリズムを ECDLP を解く Shor のアルゴリズムに適用することで，9n + [log2n｣ + 7 量子ピットと 832n3 log2n + O (n3) の Toffoli ゲートで回路を構成することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The elliptic curve discrete logarithm problem (ECDLP) is an important problem as the base of the security of elliptic curve cryptography. When solving the ECDLP in quantum computation, modular inverse is the bottleneck in terms of circuit size. In our research, two new quantum algorithms for computing modular inverse are proposed. By applying these to Shor's algorithm solving the ECDLP, more efficient quantum circuits can be implemented using 9n - [log2 n] + 7 qubits and 832n3 log2 n + O (n3) Toffoli gates.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2019-CSEC-86, 号 18, p. 1-6, 発行日 2019-07-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会