nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Improved Classical Cryptanalysis of SIKE in Practice

verfasst von : Craig Costello, Patrick Longa, Michael Naehrig, Joost Renes, Fernando Virdia

Erschienen in: Public-Key Cryptography – PKC 2020

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The main contribution of this work is an optimized implementation of the van Oorschot-Wiener (vOW) parallel collision finding algorithm. As is typical for cryptanalysis against conjectured hard problems (e. g. factoring or discrete logarithms), challenges can arise in the implementation that are not captured in the theory, making the performance of the algorithm in practice a crucial element of estimating security. We present a number of novel improvements, both to generic instantiations of the vOW algorithm finding collisions in arbitrary functions, and to its instantiation in the context of the supersingular isogeny key encapsulation (SIKE) protocol, that culminate in an improved classical cryptanalysis of the computational supersingular isogeny (CSSI) problem. In particular, we present a scalable implementation that can be applied to the Round-2 parameter sets of SIKE that can be used to give confidence in their security levels.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Faster Cofactorization with ECM Using Mixed Representations

Nächstes Kapitel A Short-List of Pairing-Friendly Curves Resistant to Special TNFS at the 128-Bit Security Level

In our scenario, many collisions are encountered before the golden collision is found. Starting new trails (rather than continuing on from distinguished points) avoids falling into cycles and repeatedly detecting the same collisions [23, p. 6, Footnote 5].

Of course, this strategy is not useful for a distributed attack on an actual cryptographically sized problem instance. It only aids the efficiency of small-sized experiments in order to get a better understanding of the algorithm.

The extreme case, when the full isogeny tree from one side is precomputed, corresponds to the meet-in-the-middle algorithm as described by Adj et al. [1].

This slightly changes how an element \(r_0 + r_12^{\varDelta }\in \mathbb {Z}_{2^{e-2}}\), for \(r_0\in \mathbb {Z}_{2^{\varDelta }}\) and \(r_1\in \mathbb {Z}_{2^{e-2-\varDelta }}\), corresponds to an isogeny. Instead of kernel \(\langle P + [r_0+r_12^{\varDelta }]Q\rangle \), it now gives rise to the kernel \(\langle P + [r_0 + r_12^{\varDelta +1}]Q\rangle \). This has no impact on the algorithm.

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 Jr., M. (eds.) SAC 2018. LNCS, pp. 322–343. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-10970-7_15CrossRef

Beazley, D.M.: SWIG: an easy to use tool for integrating scripting languages with C and C++. In: USENIX Tcl/Tk Workshop. USENIX Association (1996)

De Feo, L., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014)MathSciNetMATH

Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_p\). Des. Codes Crypt. 78(2), 425–440 (2016)MathSciNetCrossRef

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996. ACM (1996)

Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_9CrossRefMATH

Jao, D., et al.: SIKE: Supersingular isogeny key encapsulation (2017). Manuscript available at sike.org/

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_2CrossRefMATH

Jaques, S., Schanck, J.M.: Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 32–61. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_2CrossRefMATH

10.

Lenstra Jr., H.W.: Complex multiplication structure of elliptic curves. J. Number Theory 56(2), 227–241 (1996)MathSciNetCrossRef

11.

Mestre, J.-F.: La méthode des graphes. Exemples et applications. In: Proceedings of the International Conference on Class Numbers and Fundamental Units of Algebraic Number Fields (Katata), pp. 217–242 (1986)

12.

Microsoft. SIDH Library v3.0 (2015–2019). https://github.com/Microsoft/PQCrypto-SIDH

13.

Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRef

14.

National Institute of Standards and Technology. Post-quantum cryptography standardization, December 2016. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization

15.

OpenMP Architecture Review Board. OpenMP Application Program Interface Version 4.5, November 2015

16.

Petit, C.: Faster algorithms for isogeny problems using torsion point images. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 330–353. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_12CrossRef

17.

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_11CrossRef

18.

Sedgewick, R., Szymanski, T.G., Yao, A.C.: The complexity of finding cycles in periodic functions. SIAM J. Comput. 11(2), 376–390 (1982)MathSciNetCrossRef

19.

Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposium Pure Math, vol. 20, pp. 415–440 (1971)

20.

Silverman, J.H.: The Arithmetic of Elliptic Curves, vol. 106. Springer, New York (2009). https://doi.org/10.1007/978-0-387-09494-6CrossRefMATH

21.

Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: FOCS 2004, pp. 32–41. IEEE (2004)

22.

Tani, S.: Claw finding algorithms using quantum walk. Theor. Comput. Sci. 410(50), 5285–5297 (2009)MathSciNetCrossRef

23.

van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999). https://doi.org/10.1007/PL00003816MathSciNetCrossRefMATH

24.

van Vredendaal, C.: Reduced memory meet-in-the-middle attack against the NTRU private key. LMS J. Comput. Math. 19(A), 43–57 (2016)MathSciNetCrossRef

25.

Vélu, J.: Isogénies entre courbes elliptiques. Comptes Rendus de l’Académie des Sciences des Paris 273, 238–241 (1971)MathSciNetMATH

26.

Wiener, M.J.: The full cost of cryptanalytic attacks. J. Cryptol. 17(2), 105–124 (2004). https://doi.org/10.1007/s00145-003-0213-5MathSciNetCrossRefMATH

27.

Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 190–200. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48892-8_15CrossRef

Titel: Improved Classical Cryptanalysis of SIKE in Practice
verfasst von: Craig Costello
Patrick Longa
Michael Naehrig
Joost Renes
Fernando Virdia
Verlag: Springer International Publishing
Buch: Public-Key Cryptography – PKC 2020
Print ISBN: 978-3-030-45387-9

Electronic ISBN: 978-3-030-45388-6

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45388-6_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"