Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library (Part Ⅱ)

摘要

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).%補助入力付き離散対数問題（Discrete Logarithm Problem with Auxiliary Input，DLPwAI）とは，素数位数rの元Cが生成する加法群において，3つの元G，αG，α~dGとd|（r-1）を満たす正整数dとから，解となる正整数αを求める問題である．2010年に酒見等は，Cheonが提案した補助入力付き離散対数問題の解法アルゴリズム（Cheonアルゴリズム）を実装し，組込み機器向けのペアリング暗号ライブラリであるTinyTateライブラリで使用されている楕円曲線（位数rは128ビット）において，補助入力付き離散対数問題が（1コアに換算して）約131時間で解読できることを報告した．しかしCheonアルゴリズムのサブアルゴリズムとしてShanksのBSGS法（Baby-step Giant-step法）を使用していたことから，膨大な記憶容量（約246GByte）が必要であった．このため，より大きなサイズの補助入力付き離散対数問題への適用は難しいと結論付けられていた．そこで本稿は，記憶容量を抑制する目的で，サブアルゴリズムとしてPollardのρ法を使用したCheonアルゴリズムを実装し，同じ補助入力付き離散対数問題を（1コアに換算して）約136時間で解いた結果について報告する．使用した記憶容量は約0．5MByte程度であった．