Optimal strategies for CSIDH. (English) Zbl 1500.94022
Summary: Since its proposal in W. Castryck et al. [Lect. Notes Comput. Sci. 11274, 395–427 (2018; Zbl 1407.81084)], the commutative isogeny-based key exchange protocol (CSIDH) has spurred considerable attention to improving its performance and re-evaluating its classical and quantum security guarantees. In this paper we discuss how the optimal strategies employed by the Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol can be naturally extended to CSIDH. Furthermore, we report a software library that achieves moderate but noticeable performance speedups when compared against state-of-the-art implementations of CSIDH-512, which is the most popular CSIDH instantiation. We also report an estimated number of field operations for larger instantiations of this protocol, namely, CSIDH-1024 and CSIDH-1792.
MSC:
| 94A60 | Cryptography |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 14L30 | Group actions on varieties or schemes (quotients) |
Keywords:
isogeny-based cryptography; post-quantum cryptography; CSIDH protocol; key-exchange protocol; group action evaluationCitations:
Zbl 1407.81084References:
| [1] | R. Azarderakhsh, et al., Supersingular isogeny key encapsulation, Second Round Candidate of the NIST’s Post-quantum Cryptography Standardization Process, 2017, Available from: https://sike.org/. |
| [2] | D. J. Bernstein, M. Hamburg, A. Krasnova and T. Lange, Elligator: Elliptic-curve points indistinguishable from uniform random strings, in 2013 ACM SIGSAC Conference on Computer and Communications Security, 2013,967-980. |
| [3] | D. J. Bernstein, T. Lange, C. Martindale and L. Panny, Quantum circuits for the CSIDH: Optimizing quantum evaluation of isogenies, Advances in Cryptology-EUROCRYPT 2019, LNCS, 11477, 2019,409-441. · Zbl 1508.81648 |
| [4] | D. J. Bernstein, L. De Feo, A. Leroux and B. Smith, Faster computation of isogenies of large prime degree, Cryptology ePrint Archive, Report 2020/341 (2020), Available from: https://eprint.iacr.org/2020/341. · Zbl 1469.11479 |
| [5] | W. Castryck and T. Decru, CSIDH on the surface, Post-Quantum Cryptography - 11th International Conference, LNCS, 12100, 2020,111-129. · Zbl 1501.94035 |
| [6] | W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient post-quantum commutative group action, Advances in Cryptology-ASIACRYPT 2018, LNCS, 11274, 2018,395-427. · Zbl 1407.81084 |
| [7] | D. Cervantes-Vázquez, M. Chenu, J.-J. Chi-Domínguez, L. De Feo, F. Rodríguez-Henríquez and B. Smith, Stronger and faster side-channel protections for CSIDH, Progress in Cryptology - LATINCRYPT 2019, LNCS, 11774, 2019,173-193. · Zbl 1453.94067 |
| [8] | D. Cervantes-Vázquez, E. Ochoa-Jiménez and F. Rodríguez-Henríquez, Parallel strategies for SIDH: Towards computing SIDH twice as fast, Cryptology ePrint Archive, Report 2020/383 (2020), Available from: https://eprint.iacr.org/2020/383. |
| [9] | D. Cervantes-Vázquez and F. Rodríguez-Henríquez, A note on the cost of computing odd degree isogenies, Cryptology ePrint Archive, Report 2019/1373 (2019), Available from: https://eprint.iacr.org/2019/1373. |
| [10] | C. Costello and H. Hisil, A simple and compact algorithm for SIDH with arbitrary degree isogenies, Advances in Cryptology - ASIACRYPT 2017 Part II, LNCS, 10625, 2017,303-329. · Zbl 1380.94081 |
| [11] | J.-M. Couveignes, Hard homogeneous spaces, Cryptology ePrint Archive, Report 2006/291 (2006), Available from: http://eprint.iacr.org/2006/291. |
| [12] | L. De Feo; D. Jao; J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8, 209-247 (2014) · Zbl 1372.94419 · doi:10.1515/jmc-2012-0015 |
| [13] | L. De Feo, J. Kieffer and B. Smith, Towards practical key exchange from ordinary isogeny graphs, Advances in Cryptology-ASIACRYPT 2018, LNCS, 11274, 2018,365-394. · Zbl 1447.94029 |
| [14] | A. Hutchinson, J. LeGrow, B. Koziel and R. Azarderakhsh, Further Optimizations of CSIDH: A Systematic Approach to Efficient Strategies, Permutations, and Bound Vectors., Cryptology ePrint Archive, Report 2019/1121 (2019) Available from http://eprint.iacr.org/2019/1121. · Zbl 07314297 |
| [15] | A. Jalali, R. Azarderakhsh, M. Kermani and D. Jao, Towards optimized and constant-time CSIDH on embedded devices, Constructive Side-Channel Analysis and Secure Design-COSADE 2019, LNCS, 11421, 2019,215-231. · Zbl 1522.94059 |
| [16] | P. Longa, Practical quantum-resistant key exchange from supersingular isogenies and its efficient implementation, Latincrypt 2019, Invited Talk. Available at: https://latincrypt2019.cryptojedi.org/slides/latincrypt2019-patrick-longa.pdf |
| [17] | M. Meyer, F. Campos and S. Reith, On lions and elligators: An efficient constant-time implementation of CSIDH, Post-Quantum Cryptography-PQCrypto 2019, LNCS, 11505, 2019,307-325. · Zbl 1509.94123 |
| [18] | M. Meyer and S. Reith, A faster way to the CSIDH, Progress in Cryptology-INDOCRYPT 2018, LNCS, 11356, 2018,137-152. · Zbl 1407.81087 |
| [19] | T. Moriya, H. Onuki and T. Takagi, How to construct CSIDH on Edwards curves, Topics in Cryptology - CT-RSA, LNCS, 12006, 2020,512-537. · Zbl 1457.94165 |
| [20] | ”Submission requirements and evaluation criteria for the post-quantum cryptography standardization process”, National Institute of Standards and Technology, 2016, Available from https://csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf. |
| [21] | K. Nakagawa, H. Onuki, A. Takayasu and T. Takagi, \(L_1\)-Norm ball for CSIDH: Optimal strategy for choosing the secret key space, Cryptology ePrint Archive, Report 2020/181 (2020), Available from https://eprint.iacr.org/2020/181. · Zbl 1508.94061 |
| [22] | H. Onuki, Y. Aikawa, T. Yamazaki and T. Takagi, (Short Paper) A faster constant-time algorithm of CSIDH keeping two points, Advances in Information and Computer Security IWSEC, LNCS 11689, 23-33. |
| [23] | A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145 (2006), Available from http://eprint.iacr.org/2006/145. |
| [24] | A. Stolbunov, Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, Advances in Mathematics of Communication, 4, 215-235 (2010) · Zbl 1213.94136 · doi:10.3934/amc.2010.4.215 |
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.
