文献

J-GLOBAL ID：201102281807766715   整理番号：11A1363374

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

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

著者 (4件)： SAKEMI Yumi (FUJITSU LAB. Ltd., Kanagawa, JPN) ,  IZU Tetsuya (FUJITSU LAB. Ltd., Kanagawa, JPN) ,  TAKENAKA Masahiko (FUJITSU LAB. Ltd., Kanagawa, JPN) ,  YASUDA Masaya (FUJITSU LAB. Ltd., Kanagawa, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 111  号： 123(ISEC2011 9-26)  ページ： 151-158  発行年： 2011年07月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

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

シソーラス用語： 問題 ,  曲線 ,  公開鍵暗号 ,  素数 ,  Abel群 ,  アルゴリズム ,  ライブラリ【計算機】 ,  *記憶容量 ,  コンピュータセキュリティ ,  装置 ,  酔歩 ,  計算量 ,  乗算 ,  楕円曲線 ,  ペアリング暗号 ,  *暗号解析 ,  加群
準シソーラス用語： Montgomery乗算 ,  *暗号解読 ,  加法群 ,  組込み機器 ,  楕円曲線暗号 ,  *離散対数問題

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (5件)： ライブラリ ,  楕円曲線 ,  離散対数問題 ,  解読 ,  報告