Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge

UDOVENKO, Aleksei; VITTO, Giuseppe

doi:10.1007/978-3-031-58411-4_10

Download

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge

UDOVENKO, Aleksei; VITTO, Giuseppe

2024 • In Smith, Benjamin; Wu, Huapeng (Eds.) Selected Areas in Cryptography 2022

Peer reviewed

Permalink
https://hdl.handle.net/10993/49473

DOI
10.1007/978-3-031-58411-4_10

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

SIKEp182_MitM.pdf

Author postprint (571.43 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Isogenies; Cryptanalysis; SIDH; SIKE

Abstract :

[en] We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of Luxembourg and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB.

Research center :

ULHPC - University of Luxembourg: High Performance Computing

Disciplines :

Computer science

Author, co-author :

UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux ; CryptoExperts

VITTO, Giuseppe ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux

External co-authors :

yes

Language :

English

Title :

Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge

Publication date :

2024

Event name :

Selected Areas in Cryptography (SAC 2022)

Event place :

Windsor, Ontario, Canada

Event date :

from 24-08-2022 to 26-08-2022

Audience :

International

Main work title :

Selected Areas in Cryptography 2022

Editor :

Smith, Benjamin

Wu, Huapeng

Publisher :

Springer

ISBN/EAN :

978-3-031-58411-4
978-3-031-58410-7

Peer reviewed :

Peer reviewed

Focus Area :

Computational Sciences

Additional URL :

https://ia.cr/2021/1421

FnR Project :

FNR11684537 - Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts, 2017 (01/08/2018-31/07/2021) - Alex Biryukov

Funders :

FNR - Fonds National de la Recherche

Available on ORBilu :

since 11 January 2022

Statistics

Number of views

124 (15 by Unilu)

Number of downloads

49 (2 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson, M.J., Jr. (eds.) SAC 2018. LNCS, vol. 11349, pp. 322–343. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-10970-7_15
Bernstein, D.: Cost analysis of hash collisions: will quantum computers make SHARCS obsolete? In: SHARCS’09 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, 9-10 September 2009), pp. 105–116 (2009)
Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 303–329. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_11
Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 572–601. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_21
Costello, C., Longa, P., Naehrig, M., Renes, J., Virdia, F.: Improved classical cryptanalysis of SIKE in practice. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 505–534. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_18
Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006)
Feo, L.D., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014)
Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118–138 (1999)
Jao, D., et al.: Supersingular Isogeny Key Encapsulation. NIST Post-Quantum Cryptography Round 3 - Alternate Candidate (2020). https://sike.org/files/SIDH-spec.pdf
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Longa, P., Wang, W., Szefer, J.: The cost to break SIKE: a comparative hardware-based analysis with AES and SHA-3. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 402–431. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_14
Microsoft Research: SIKE Cryptographic Challenge (2021). https://www.microsoft.com/en-us/msrc/sike-cryptographic-challenge
National Institute of Standards and Technology (NIST): Post-Quantum Cryptography Standardization (2016–2022). https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
Renes, J.: Computing isogenies between Montgomery curves using the action of (0, 0). In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 229–247. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_11
Rostovtsev, A., Stolbunov, A.: Public-Key Cryptosystem Based On Isogenies. Cryptology ePrint Archive, Report 2006/145 (2006)
Schnorr, C.P., Shamir, A.: An optimal sorting algorithm for mesh connected computers. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 255–263. STOC 1986, Association for Computing Machinery, New York, NY, USA (1986)
Schoof, R.: Nonsingular plane cubic curves over finite fields. J. Comb. Theory Ser. A 46(2), 183–211 (1987). https://www.sciencedirect.com/science//pii/0097316587900033
Silverman, J.: The Arithmetic of Elliptic Curves, vol. 106 (2009)
Stolbunov, A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215–235 (2010)
Tate, J.: Endomorphisms of abelian varieties over finite fields. Invent. Math. 2(2), 134–144 (1966)
The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.4) (2021). https://www.sagemath.org
The SIDH Library Developers: SIDH v3.4 (C Edition) (2021). https://github.com/microsoft/PQCrypto-SIDH
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)
Varrette, S., Bouvry, P., Cartiaux, H., Georgatos, F.: Management of an academic HPC cluster: The UL experience. In: Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS 2014), pp. 959–967. IEEE, Bologna, Italy (2014)