Abstract
There is a recent trend in cryptography to construct protocols based on the hardness of computing isogenies between supersingular elliptic curves. Two prominent examples are Jao-De Feo’s key exchange protocol and the resulting encryption scheme by De Feo-Jao-Plût. One particularity of the isogeny problems underlying these protocols is that some additional information is given as input, namely the image of some torsion points with order coprime to the isogeny. This additional information was used in several active attacks against the protocols but the current best passive attacks make no use of it at all.
In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to heuristic polynomial-time key recovery on two non-standard variants of De Feo-Jao-Plût’s protocols in plausible attack models. This shows that at least some isogeny problems are easier to solve when additional information is leaked.
In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to heuristic polynomial-time key recovery on two non-standard variants of De Feo-Jao-Plût’s protocols in plausible attack models. This shows that at least some isogeny problems are easier to solve when additional information is leaked.
Original language | English |
---|---|
Title of host publication | Advances in Cryptology – ASIACRYPT 2017 |
Subtitle of host publication | 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II |
Editors | Tsuyoshi Takagi, Thomas Peyrin |
Publisher | Springer |
Pages | 330-353 |
Number of pages | 24 |
ISBN (Electronic) | 9783319706979 |
ISBN (Print) | 9783319706962 |
DOIs | |
Publication status | Published - 18 Nov 2017 |
Event | 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017) - Hong Kong Duration: 3 Dec 2017 → 7 Dec 2017 |
Publication series
Name | Lecture Notes in Computer Science (LNCS) |
---|---|
Publisher | Springer |
Volume | 10625 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017) |
---|---|
City | Hong Kong |
Period | 3/12/17 → 7/12/17 |