Faster algorithms for isogeny problems using torsion point images. (English) Zbl 1409.94898
Takagi, Tsuyoshi (ed.) et al., Advances in cryptology – ASIACRYPT 2017. 23rd international conference on the theory and applications of cryptology and information security, Hong Kong, China, December 3–7, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10625, 330-353 (2017).
Summary: 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 L. De Feo et al. [PQCrypto 2011, Lect. Notes Comput. Sci. 7071, 19–34 (2011; Zbl 1290.94094); J. Math. Cryptol. 8, No. 3, 209–247 (2014; Zbl 1372.94419)]. 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.
For the entire collection see [Zbl 1380.94007].
For the entire collection see [Zbl 1380.94007].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Ankeny, NC, The least quadratic non residue, Ann. Math., 55, 1, 65-72, 1952 · Zbl 0046.04006 · doi:10.2307/1969420 |
| [2] | Charles, DX; Lauter, KE; Goren, EZ, Cryptographic hash functions from expander graphs, J. Cryptol., 22, 1, 93-113, 2009 · Zbl 1166.94006 · doi:10.1007/s00145-007-9002-x |
| [3] | Coggia, D.: Implémentation d’une variante du protocole de key-exchange SIDH (2017). https://github.com/dnlcog/sidh_variant |
| [4] | Costello, C.; Longa, P.; Naehrig, M.; Robshaw, M.; Katz, J., Efficient algorithms for supersingular isogeny Diffie-Hellman, Advances in Cryptology - CRYPTO 2016, 572-601, 2016, Heidelberg: Springer, Heidelberg · Zbl 1384.94046 · doi:10.1007/978-3-662-53018-4_21 |
| [5] | Cremona, JE; Rusin, D., Efficient solution of rational conics, Math. Comput., 72, 243, 1417-1441, 2003 · Zbl 1022.11031 · doi:10.1090/S0025-5718-02-01480-1 |
| [6] | Delfs, C.; Galbraith, SD, Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_p\), Des. Codes Crypt., 78, 2, 425-440, 2016 · Zbl 1361.11044 · doi:10.1007/s10623-014-0010-1 |
| [7] | Feo, LD; Jao, D.; Plût, J., Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., 8, 3, 209-247, 2014 · Zbl 1372.94419 |
| [8] | Galbraith, SD; Petit, C.; Shani, B.; Ti, YB; Cheon, JH; Takagi, T., On the security of supersingular isogeny cryptosystems, Advances in Cryptology - ASIACRYPT 2016, 63-91, 2016, Heidelberg: Springer, Heidelberg · Zbl 1404.94073 · doi:10.1007/978-3-662-53887-6_3 |
| [9] | Galbraith, SD; Petit, C.; Silva, J.; Takagi, T.; Peyrin, T., Identification protocols and signature schemes based on supersingular isogeny problems, ASIACRYPT 2017, Part I, 3-33, 2017, Cham: Springer, Cham · Zbl 1420.94065 |
| [10] | Gélin, A.; Wesolowski, B.; Lange, T.; Takagi, T., Loop-abort faults on supersingular isogeny cryptosystems, Post-Quantum Cryptography, 93-106, 2017, Cham: Springer, Cham · Zbl 1437.94065 · doi:10.1007/978-3-319-59879-6_6 |
| [11] | Jao, D.; De Feo, L.; Yang, B-Y, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography, 19-34, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94094 · doi:10.1007/978-3-642-25405-5_2 |
| [12] | Kohel, D.: Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California, Berkeley (1996) |
| [13] | Kohel, D.; Lauter, K.; Petit, C.; Tignol, J-P, On the quaternion \(\ell \)-isogeny path problem, LMS J. Comput. Math., 17A, 418-432, 2014 · Zbl 1296.11153 · doi:10.1112/S1461157014000151 |
| [14] | Petit, C.: Faster algorithms for isogeny problems using torsion point images. IACR Cryptology ePrint Archive, 2017:571 (2017) |
| [15] | Petit, C., Lauter, K.: Hard and easy problems in supersingular isogeny graphs (2017) |
| [16] | Canfield, R.; Erdös, P.; Pomerance, C., On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory, 17, 1-28, 1983 · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1 |
| [17] | Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). http://eprint.iacr.org/ |
| [18] | Silverman, J., The Arithmetic of Elliptic Curves, 1986, New York: Springer Verlag, New York · Zbl 0585.14026 · doi:10.1007/978-1-4757-1920-8 |
| [19] | Simon, D.: Quadratic equations in dimensions 4, 5 and more. Preprint (2005). http://www.math.unicaen.fr/ simon/ |
| [20] | Ti, YB; Lange, T.; Takagi, T., Fault attack on supersingular isogeny cryptosystems, Post-Quantum Cryptography, 107-122, 2017, Cham: Springer, Cham · Zbl 1437.94075 · doi:10.1007/978-3-319-59879-6_7 |
| [21] | Vignéras, M-F, Arithmétique des Algèbres de Quaternions, 2006, Heidelberg: Springer, Heidelberg |
| [22] | Fieker, C., Steel, A., Bosma, W., Cannon, J.J. (eds.): Handbook of Magma functions, edition 2.20 (2013). http://magma.maths.usyd.edu.au/magma/ |
| [23] | Xi, S.; Tian, H.; Wang, Y., Toward quantum-resistant strong designated verifier signature from isogenies, Int. J. Grid Util. Comput., 5, 2, 292-296, 2012 |
| [24] | Yoo, Y., Azarderakhsh, R., Jalali, A., Jao, D., Soukharev, V.: A post-quantum digital signature scheme based on supersingular isogenies. Financial Crypto (2017) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
