量子FLT逆元計算アルゴリズムの改良

• Item type: Symposium(1)
• 公開日: 2022-10-17
• タイトル: 量子FLT逆元計算アルゴリズムの改良
• タイトル / 言語: en
• タイトル: Improved quantum FLT-based inversion Algorithm
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ECDLP，量子アルゴリズム，FLT 逆元計算，リソース評価，加法連鎖
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology,The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology,The University of Tokyo
• 著者名: 田口, 廉; 高安, 敦
• 著者名(英): Ren, Taguchi; Atsushi, Takayasu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 楕円曲線上の離散対数問題（elliptic curve discrete logarithm problem, ECDLP）は Shor の量子アルゴリズムによって多項式時間で解けることが知られており，実装に係るリソースの見積りと削減は重要な研究課題である．本研究はバイナリ楕円曲線上の ECDLP を対象とし，特に最も支配的な F*2n 上の逆元計算を行う方法の一つである量子 FLT 逆元計算に注目する．Banegas らと Putranto らはそれぞれ量子ビット数と深さの最適化を目指した量子 FLT 逆元計算アルゴリズムを提案した．本論文で，我々は 2 つの改良アルゴリズムを提案し，NIST の推奨する次数 n において既存研究とリソース数を比較する．1 つ目の提案アルゴリズムは，全ての n において Putranto らのアルゴリズムの量子ゲート数・深さを犠牲にすることなく量子ビット数を削減しており，特に n = 409, 571 のときには量子ゲート数をも削減する．2 つ目の提案アルゴリズムは，全ての n において Banegas らのアルゴリズムの量子ビット数・量子ゲート数を犠牲にすることなく深さを削減し，特に n = 409, 571 のときには量子ビット数・量子ゲート数をも削減する．提案アルゴリズムは，既存研究がいずれも Itoh-Tsujii 古典 FLT 逆元計算を基にしていたのに対して，より一般的な加法連鎖列による FLT 逆元計算を基にしている．そして，古典計算では計算コストに影響を与えなかった加法連鎖列の性質が量子計算ではリソース数を変化させることを明らかにし，その事実に基づいて最適化を行うことで前述の改良を達成している．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Shor’s quantum algorithm solves the elliptic elliptic curve discrete logarithm problem (ECDLP) in polynomial time. FLT-based inversion is a method for computing an inverse over F2n , where the compu- tation is a dominant part of Shor’s algorithm. Banegas et al.’s algorithm and Putranto et al.’s algorithm are designed to optimize the number of qubits and the number of quantum gates, depth of circuits, respectively. In this paper, we propose two improved quantum FLT-based inversion algorithms. The first algorithm re- duces the number of qubits of Putranto et al.’s algorithm, while the second algorithm reduces the depth of Banegas et al.’s algorithm. In particular, when n = 409, 571, the first and second algorithms also reduce the number of qubits and the gates.
• 書誌情報: コンピュータセキュリティシンポジウム2022論文集; p. 981-988, 発行日 2022-10-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会