| Presentation | 2017-03-09 Security Analysis of Ordinary Isogeny Diffie--Hellman Satoshi Furukawa, Atsushi Takayasu, Noboru Kunihiro, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we analyze the security of Ordinary Isogeny Diffie--Hellman (OIDH) key exchange proposed by Stolbunov (Adv. Math. Commun. 2010). In particular, we consider a problem to compute the OIDH shared key from partial information (e.g. most significant bits) on the shared key. First, we define the Isogeny Hidden Number Problem (IHNP) which proposed by Galbraith {it et al.} (Asiacrypt 2016) for ordinary elliptic curves. Next, we propose the algorithm to solve IHNP for ordinary elliptic curves in polynomial time by using Coppersmith's method (Eurocrypt'96) for finding roots of modular equations. Our algorithm can recover the entire OIDH shared key in polynomial time if we get more than $6/7$ most significant bits of the shared key. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Elliptic curve / Isogeny / OIDH key exchange / Coppersmith's method |
| Paper # | IT2016-104,ISEC2016-94,WBS2016-80 |
| Date of Issue | 2017-03-02 (IT, ISEC, WBS) |
| Conference Information | |
| Committee | ISEC / WBS / IT |
|---|---|
| Conference Date | 2017/3/9(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | TOKAI University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | joint meeting of IT, ISEC, and WBS |
| Chair | Masahiro Mambo(Kanazawa Univ.) / Fumiaki Maehara(Waseda Univ.) / Masayoshi Ohashi(Fukuoka Univ.) |
| Vice Chair | Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Masanori Hamamura(Kochi Univ. of Tech.) / Fumie Ono(NICT) / Jun Muramatsu(NTT) |
| Secretary | Kazuto Ogawa(Toshiba) / Atsushi Fujioka(Tohoku Univ.) / Masanori Hamamura(Tokyo City Univ.) / Fumie Ono(Mitsubishi Electric) / Jun Muramatsu(Wakayama Univ.) |
| Assistant | Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Yusuke Kozawa(Tokyo Univ. of Science) / Akira Nakamura(Tokyo Univ. of Science) / Ryohei Nakamura(National Defense Academy) / Mitsugu Iwamoto(Univ. of Electro-Comm.) |
| Paper Information | |
| Registration To | Technical Committee on Information Security / Technical Committee on Wideband System / Technical Committee on Information Theory |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Security Analysis of Ordinary Isogeny Diffie--Hellman |
| Sub Title (in English) | |
| Keyword(1) | Elliptic curve |
| Keyword(2) | Isogeny |
| Keyword(3) | OIDH key exchange |
| Keyword(4) | Coppersmith's method |
| 1st Author's Name | Satoshi Furukawa |
| 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(The Univ. of Tokyo) |
| 3rd Author's Name | Noboru Kunihiro |
| 3rd Author's Affiliation | The University of Tokyo(The Univ. of Tokyo) |
| Date | 2017-03-09 |
| Paper # | IT2016-104,ISEC2016-94,WBS2016-80 |
| Volume (vol) | vol.116 |
| Number (no) | IT-504,ISEC-505,WBS-506 |
| Page | pp.pp.33-40(IT), pp.33-40(ISEC), pp.33-40(WBS), |
| #Pages | 8 |
| Date of Issue | 2017-03-02 (IT, ISEC, WBS) |