| Presentation | 2017-11-10 Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange Sota Onozawa, Atsushi Takayasu, Noboru Kunihiro, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | ISEC2017-69,SITE2017-51,LOIS2017-46 |
| Date of Issue | 2017-11-02 (ISEC, SITE, LOIS) |
| Conference Information | |
| Committee | LOIS / ISEC / SITE |
|---|---|
| Conference Date | 2017/11/9(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroyuki Nishi(Sojo Univ.) / Kazuto Ogawa(NHK) / Hitoshi Okada(NII) |
| Vice Chair | Tomohiro Yamada(NTT) / Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) |
| Secretary | Tomohiro Yamada(Nagasaki Univ.) / Atsushi Fujioka(NTT) / Shiho Moriai(Tohoku Univ.) / Tetsuya Morizumi(Tokai Univ.) / Masaru Ogawa(Gifu Shotoku Gakuen Univ.) |
| Assistant | Motoi Okamoto(Research Organization of Information and Systems) / Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) / Akiyoshi Kabeya(Chiba Univ.) / Hisanori Kato(KDDI) |
| Paper Information | |
| Registration To | Technical Committee on Life Intelligence and Office Information Systems / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Lattice Attacks on Elliptic Curve Diffie-Hellman key exchange |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Sota Onozawa |
| 1st Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
| 2nd Author's Name | Atsushi Takayasu |
| 2nd Author's Affiliation | The University of Tokyo/National Institute of Advanced Industrial Science and Technology(The Univ. of Tokyo/AIST) |
| 3rd Author's Name | Noboru Kunihiro |
| 3rd Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
| Date | 2017-11-10 |
| Paper # | ISEC2017-69,SITE2017-51,LOIS2017-46 |
| Volume (vol) | vol.117 |
| Number (no) | ISEC-285,SITE-286,LOIS-287 |
| Page | pp.pp.115-122(ISEC), pp.115-122(SITE), pp.115-122(LOIS), |
| #Pages | 8 |
| Date of Issue | 2017-11-02 (ISEC, SITE, LOIS) |