文献

J-GLOBAL ID：201702232882874014   整理番号：17A1942942

楕円曲線Diffie-Hellman鍵共有に対する格子簡約攻撃

Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange

著者 (4件)： 小野澤綜大 (東大) ,  高安敦 (東大) ,  高安敦 (産業技術総合研) ,  國廣昇 (東大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 117  号： 285(ISEC2017 49-71)  ページ： 115-122  発行年： 2017年11月02日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 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回クエリすることで鍵を復元することも示す。(著者抄録)

シソーラス用語： 計算機網 ,  *暗号鍵 ,  *情報共有 ,  情報 ,  *回復 ,  近似法 ,  縮小 ,  アルゴリズム ,  公開鍵暗号 ,  *攻撃行動 ,  *サイバー攻撃
準シソーラス用語： LLLアルゴリズム ,  *鍵回復 ,  *鍵共有 ,  多項式時間アルゴリズム ,  楕円曲線暗号 ,  秘密鍵 ,  不完全情報 ,  *情報攻撃

分類 (1件)： 計算機網  (JC03000K)

引用文献 (25件)：

• Don Coppersmith. Finding small solutions to small degree polynomials. In Proc. of EUROCRYPT, pp. 155-165, 1996.
• Nicholas Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Proc. of Cryptography and Coding, pp. 131-142, 1997.
• Dan Boneh, Ramarathnam Venkatesan. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In Proc. of CRYPTO, pp. 129-142, 1996.
• Barak Shani. On the bit security of elliptic curve Diffie-Hellman. In Proc. of PKC, pp. 361-387, 2017.
• Arjen K. Lenstra, Hendrick W. Lenstra Jr and L?szl? Lov?sz. Factoring polynomials with rational coefficients. Math. Ann., Vol. 261, pp. 513-534, 1982.

タイトルに関連する用語 (5件)： 楕円曲線 ,  Diffie-Hellman鍵共有 ,  格子 ,  簡約 ,  攻撃