| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-11-10 15:10 楕円曲線Diffie-Hellman鍵共有に対する格子簡約攻撃 ○小野澤綜大（東大）・高安 敦（東大/産総研）・國廣 昇（東大）  ISEC2017-69 SITE2017-51 LOIS2017-46 |
|
| 抄録 | （和） | Boneh と Venkatesan (CRYPTO’96) は Diffie-Hellman 鍵共有において鍵情報が部分的に漏洩した時の安全性評価として hidden number problem (HNP) を提案した． HNP は Diffie-Hellman 鍵共有によって共有した鍵の部分情報を出力するオラクルを用いて，鍵を復元する問題である． Shani (PKC’17) は楕円曲線 Diffie-Hellman 鍵共有における HNP (EC-HNP) の解析を初めて行った． Shani は EC-HNP を法付き連立方程式に帰着させ，格子簡約アルゴリズムを用いてその方程式を解く deterministic な多項式時間アルゴリズムを提案した．このアルゴリズムは鍵の上位ビットの約83 %を出力するオラクルに十分多くクエリすることで鍵を多項式時間で復元する．本研究では， Coppersmith の手法を用いた多項式時間アルゴリズムを提案する． EC-HNP を Shani らが用いなかった高次な法付き方程式に帰着させて解くことで改良する．そして， heuristic だが上位ビットの約65 %を出力するオラクルに 11 回クエリすることで，鍵を復元することを示す．また，提案手法は上位ビットの約78 %を出力するオラクルに 3 回クエリすることで鍵を復元することも示す． |
| （英） | Boneh and Venkatesan (Crypto’96) introduced the hidden number problem (HNP) to study the security of Diffie-Hellman key exchange protocol by assuming exposures of partial information. In short, an HNP solver tries to recover a shared key through the protocol by issuing adaptive queries to an oracle who answers partial information of shared keys. Shani (PKC’17) first studied an elliptic curve HNP (EC-HNP) to study the security of elliptic curve Diffie-Hellman key exchange protocol. He reduced the EC-HNP to simultaneous modular equations then proposed a deterministic key recovery algorithm that utilized lattice-reduction algorithms. If an EC-HNP oracle answers about 83 % most significant bits (MSBs) of shared keys sufficiently many times, the algorithm works in polynomial time.In this work, we improves the attack by using lattice-based Coppersmith’s method. We show that higher degree polynomials, which were not used in previous works, are useful to obtain better results. Concretely, although our proposed algorithm is heuristic, it works in polynomial time by assuming an oracle who answers about 65 % MSBs only 11 times. Furthermore, even if the number of queries is only 3 times, our algorithm works in polynomial time with about 78 % MSBs. Therefore, our attack requires a weaker oracle than Shani’s attack; less number of queries and less partial information. | |
| キーワード | （和） | / / / / / / / |
| （英） | / / / / / / / | |
| 文献情報 | 信学技報, vol. 117, no. 285, ISEC2017-69, pp. 115-122, 2017年11月. | |
| 資料番号 | ISEC2017-69 | |
| 発行日 | 2017-11-02 (ISEC, SITE, LOIS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2017-69 SITE2017-51 LOIS2017-46 |
|
| 研究会情報 | |
| 研究会 | LOIS ISEC SITE |
| 開催期間 | 2017-11-09 - 2017-11-10 |
| 開催地（和） | 京都産業大学むすびわざ館 |
| 開催地（英） | |
| テーマ（和） | 情報セキュリティ，ライフログ活用技術，ライフインテリジェンス，オフィス情報システム，一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2017-11-LOIS-ISEC-SITE |
| 本文の言語 | 日本語 |
| タイトル（和） | 楕円曲線Diffie-Hellman鍵共有に対する格子簡約攻撃 |
| サブタイトル（和） | |
| タイトル（英） | Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / |
| キーワード(2)（和/英） | / |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 小野澤 綜大 / Sota Onozawa / オノザワ ソウタ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） | 高安 敦 / Atsushi Takayasu / タカヤス アツシ |
| 第2著者 所属（和/英） | 東京大学/産業技術総合研究所 (略称： 東大/産総研) The University of Tokyo/National Institute of Advanced Industrial Science and Technology (略称： The Univ. of Tokyo/AIST) |
| 第3著者 氏名（和/英/ヨミ） | 國廣 昇 / Noboru Kunihiro / クニヒロ ノボル |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： The Univ. of Tokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-11-10 15:10:00 |
| 発表時間 | 30分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2017-69, SITE2017-51, LOIS2017-46 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.285(ISEC), no.286(SITE), no.287(LOIS) |
| ページ範囲 | pp.115-122 |
| ページ数 | 8 |
| 発行日 | 2017-11-02 (ISEC, SITE, LOIS) |
[研究会発表申込システムのトップページに戻る]