| 講演名 | 2011-07-13 TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般) 酒見 由美, 伊豆 哲也, 武仲 正彦, 安田 雅哉, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 補助入力付き離散対数問題(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法)を使用していたことから,膨大な記憶容量(約246GByte)が必要であった.このため,より大きなサイズの補助入力付き離散対数問題への適用は難しいと結論付けられていた.そこで本稿は,記憶容量を抑制する目的で,サブアルゴリズムとしてPollardのρ法を使用したCheonアルゴリズムを実装し,同じ補助入力付き離散対数問題を(1コアに換算して)約136時間で解いた結果について報告する.使用した記憶容量は約0.5MByte程度であった. |
| 抄録(英) | 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). |
| キーワード(和) | 補助入力付き離散対数問題(DLPPwAI) / Cheonアルゴリズム / 実装 / TinyTateライブラリ |
| キーワード(英) | Discrete logarithm problem with auxiliary input(DLPwAI) / Cheon's algorithm / implementation / TinyTate library |
| 資料番号 | ISEC2011-26,SITE2011-23,ICSS2011-31,EMM2011-25 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SITE |
|---|---|
| 開催期間 | 2011/7/5(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Social Implications of Technology and Information Ethics (SITE) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | TinyTateライブラリが使用する楕円曲線における補助入力付き離散対数問題の解読報告(その2)(セキュリティ関係,一般) |
| サブタイトル（和） | |
| タイトル（英） | Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library(Part II) |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 補助入力付き離散対数問題(DLPPwAI) / Discrete logarithm problem with auxiliary input(DLPwAI) |
| キーワード(2)（和/英） | Cheonアルゴリズム / Cheon's algorithm |
| キーワード(3)（和/英） | 実装 / implementation |
| キーワード(4)（和/英） | TinyTateライブラリ / TinyTate library |
| 第 1 著者 氏名（和/英） | 酒見 由美 / Yumi SAKEMI |
| 第 1 著者 所属（和/英） | 株式会社富士通研究所セキュアコンピューティング研究部 FUJITSU LABORATORIES Ltd., Secure Computing Lab. |
| 第 2 著者 氏名（和/英） | 伊豆 哲也 / Tetsuya IZU |
| 第 2 著者 所属（和/英） | 株式会社富士通研究所セキュアコンピューティング研究部 FUJITSU LABORATORIES Ltd., Secure Computing Lab. |
| 第 3 著者 氏名（和/英） | 武仲 正彦 / Masahiko TAKENAKA |
| 第 3 著者 所属（和/英） | 株式会社富士通研究所セキュアコンピューティング研究部 FUJITSU LABORATORIES Ltd., Secure Computing Lab. |
| 第 4 著者 氏名（和/英） | 安田 雅哉 / Masaya YASUDA |
| 第 4 著者 所属（和/英） | 株式会社富士通研究所セキュアコンピューティング研究部 FUJITSU LABORATORIES Ltd., Secure Computing Lab. |
| 発表年月日 | 2011-07-13 |
| 資料番号 | ISEC2011-26,SITE2011-23,ICSS2011-31,EMM2011-25 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 124 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |