@techreport{oai:ipsj.ixsq.nii.ac.jp:00075033,
 author = {酒見, 由美 and 伊豆, 哲也 and 武仲, 正彦 and 安田, 雅哉 and Yumi, Sakemi and Tetsuya, Izu and Masahiko, Takenaka and Masaya, Yasuda},
 issue = {24},
 month = {Jul},
 note = {補助入力付き離散対数問題 (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 程度であった．, 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).},
 title = {TinyTate ライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告（その2）},
 year = {2011}
}