TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告（その2）

• Item type: SIG Technical Reports(1)
• 公開日: 2011-07-05
• タイトル: TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告（その2）
• タイトル / 言語: en
• タイトル: Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library (Part II)
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 株式会社富士通研究所セキュアコンピューティング研究部
• 著者所属: 株式会社富士通研究所セキュアコンピューティング研究部
• 著者所属: 株式会社富士通研究所セキュアコンピューティング研究部
• 著者所属: 株式会社富士通研究所セキュアコンピューティング研究部
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES Ltd., Secure Computing Lab.
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES Ltd., Secure Computing Lab.
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES Ltd., Secure Computing Lab.
• 著者所属(英): en
• 著者所属(英): FUJITSU LABORATORIES Ltd., Secure Computing Lab.
• 著者名: 酒見, 由美; 伊豆, 哲也; 武仲, 正彦; 安田, 雅哉
• 著者名(英): Yumi, Sakemi; Tetsuya, Izu; Masahiko, Takenaka; Masaya, Yasuda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 補助入力付き離散対数問題 (Discrete Logarithm Problem with Auxiliary Input，DLPwAI) とは，素数位数 r の元 G が生成する加法群において，3 つの元 G，αG，αdG と d|(r − 1) を満たす正整数 d とから，解となる正整数 α を求める問題である．2010 年に酒見等は，Cheon が提案した補助入力付き離散対数問題の解法アルゴリズム (Cheon アルゴリズム) を実装し，組込み機器向けのペアリング暗号ライブラリである TinyTate ライブラリで使用されている楕円曲線 (位数 r は 128 ビット) において，補助入力付き離散対数問題が (1 コアに換算して) 約 131 時間で解読できることを報告した．しかし Cheon アルゴリズムのサブアルゴリズムとして Shanks の BSGS 法 (Baby-step Giant-step 法) を使用していたことから，膨大な記憶容量 (約 246 GByte) が必要であった．このため，より大きなサイズの補助入力付き離散対数問題への適用は難しいと結論付けられていた．そこで本稿は，記憶容量を抑制する目的で，サブアルゴリズムとして Pollard の ρ 法を使用した Cheon アルゴリズムを実装し，同じ補助入力付き離散対数問題を (1 コアに換算して) 約 136 時間で解いた結果について報告する．使用した記憶容量は約 0.5 MByte 程度であった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find a positive integer α from elements G, αG, αdG in an additive cyclic group generated by G of prime order r and a positive integer d dividing r − 1. In 2010, Sakemi et al. implemented Cheon’s algorithm for solving DLPwAI, and solved a DLPwAI in a group with 128-bit order r in about 131 hours with a single core on an elliptic curve defined over a prime finite field which is used in the TinyTate library for embedded cryptographic devices. However, since their implementation was based on Shanks’ Baby-step Giant-step (BSGS) algorithm as a sub-algorithm, it required a large amount of memory (246 GByte) so that it was concluded that applying other DLPwAIs with larger parameter is infeasible. In this article, we implemented Cheon’s algorithm based on Pollard’s ρ-algorithm in order to reduce the required memory. As a result, we have succeeded solving the same DLPwAI in about 136 hours by a single core with less memory (0.5 MByte).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2011-CSEC-54, 号 24, p. 1-8, 発行日 2011-07-05
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会