nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

A Note on the Security of CSIDH

verfasst von : Jean-François Biasse, Annamaria Iezzi, Michael J. Jacobson Jr.

Erschienen in: Progress in Cryptology – INDOCRYPT 2018

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

We propose a quantum algorithm for computing an isogeny between two elliptic curves \(E_1,E_2\) defined over a finite field such that there is an imaginary quadratic order \(\mathcal {O}\) satisfying \(\mathcal {O}\simeq {\text {End}}(E_i)\) for \(i = 1,2\). This concerns ordinary curves and supersingular curves defined over \(\mathbb {F}_p\) (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time \(e^{O\left( \sqrt{\log (|\varDelta |)}\right) }\) and requires polynomial quantum memory and \(e^{O\left( \sqrt{\log (|\varDelta |)}\right) }\) quantumly accessible classical memory, where \(\varDelta \) is the discriminant of \(\mathcal {O}\). This asymptotic complexity outperforms all other available methods for computing isogenies.

We also show that a variant of our method has asymptotic run time \(e^{\tilde{O}\left( \sqrt{\log (|\varDelta |)}\right) }\) while requesting only polynomial memory (both quantum and classical).

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 A Faster Way to the CSIDH

Nächstes Kapitel Constructing Canonical Strategies for Parallel Implementation of Isogeny Based Cryptography

Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.-J., Menezes, A., Rodríguez-Henríquez, F.: The cost of computing isogenies between supersingular elliptic curves. Cryptology ePrint Archive, Report 2018/313 (2018). https://eprint.iacr.org/2018/313

Azarderakhsh, R., Jao, D., Leonardi, C.: Post-quantum static-static key agreement using multiple protocol instances. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 45–63. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_3CrossRef

Bennett, C.H.: Time/space trade-offs for reversible computation. SIAM J. Comput. 18(4), 766–776 (1989)MathSciNetCrossRef

Biasse, J.-F., Fieker, C., Jacobson Jr., M.J.: Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation. LMS J. Comput. Math. 19(A), 371–390 (2016)MathSciNetCrossRef

Biasse, J.-F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428–442. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13039-2_25CrossRef

Biasse, J.-F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10–12 January 2016, pp. 893–902. SIAM (2016)

Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH and ordinary isogeny-based schemes. Cryptology ePrint Archive, Report 2018/537 (2018). https://eprint.iacr.org/2018/537

Bosma, W., Stevenhagen, P.: On the computation of quadratic 2-class groups. Journal de Théorie des Nombres de Bordeaux 8(2), 283–313 (1996)MathSciNetCrossRef

Bröker, R., Charles, D., Lauter, K.: Evaluating large degree isogenies and applications to pairing based cryptography. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 100–112. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85538-5_7CrossRefMATH

10.

Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. Cryptology ePrint Archive, Report 2018/383 (2018). https://eprint.iacr.org/2018/383. to appear in Asiacrypt 2018

11.

Childs, A., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1–29 (2013)MathSciNetCrossRef

12.

Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138, p. xii+534. Springer, Berlin (1993). https://doi.org/10.1007/978-3-662-02945-9CrossRefMATH

13.

Couveignes, J.-M.: Hard homogeneous spaces. http://eprint.iacr.org/2006/291

14.

Diffie, W., Helman, M.: New directions in cryptography. IEEE Trans. Inf. Soc. 22(6), 644–654 (1976)MathSciNetCrossRef

15.

Feo, L.D., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. Cryptology ePrint Archive, Report 2018/485 (2018). https://eprint.iacr.org/2018/485. to appear in Asiacrypt 2018

16.

Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS weil descent attack. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 29–44. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_3CrossRef

17.

Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3CrossRef

18.

Gauß, C.F., Waterhouse, W.C.: Disquisitiones Arithmeticae. Springer, New York (1986). https://doi.org/10.1007/978-1-4939-7560-0. translated by A.A. ClarkCrossRef

19.

Hafner, J., McCurley, K.: A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2, 839–850 (1989)MathSciNetCrossRef

20.

Hamdy, S., Saidak, F.: Arithmetic properties of class numbers of imaginary quadratic fields. JP J. Algebra Number Theory Appl. 6(1), 129–148 (2006)MathSciNetMATH

21.

Hanrot, G., Pujol, X., Stehlé, D.: Terminating BKZ. IACR Cryptology ePrint Archive 2011, 198 (2011)

22.

Hanrot, G., Stehlé, D.: Improved analysis of kannan’s shortest lattice vector algorithm. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170–186. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_10CrossRef

23.

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

24.

Jao, D., LeGrow, J., Leonardi, C., Ruiz-Lopez, L.: A subexponential-time, polynomial quantum space algorithm for inverting the cm action. In: Slides of Presentation at the MathCrypt Conference (2018). https://drive.google.com/file/d/15nkb9j0GKyLujYfAb8Sfz3TjBY5PWOCT/view

25.

Kabatyanskii, A., Levenshtein, V.: Bounds for packings. On a sphere and in space. Proulcmy Peredacha informatsü 14, 1–17 (1978)MathSciNetMATH

26.

Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Johnson, D., et al. (eds.) Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA, pp. 193–206. ACM (1983)

27.

Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Severini, S., Brandão, F. (eds.) 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21–23, 2013, Guelph, Canada, vol. 22 of LIPIcs, pp. 20–34. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)

28.

Nagell, T.: Über die Klassenzahl imaginär-quadratischer Zahlkörper. Abh. Math. Sem. Univ. Hamburg 1, 140–150 (1922)MathSciNetCrossRef

29.

National Institute of Standards and Technology. Post quantum cryptography project (2018). https://csrc.nist.gov/projects/post-quantum-cryptography

30.

Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. arXiv:quant-ph/0406151

31.

Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(2), 181–199 (1994)MathSciNetCrossRef

32.

Shanks, D.: Gauss’s ternary form reduction and the 2-sylow subgroup. Math. Comput. 25(116), 837–853 (1971)MathSciNetMATH

33.

Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106, p. xii+400. Springer, New York (1992). https://doi.org/10.1007/978-1-4757-1920-8CrossRef

34.

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)MathSciNetCrossRef

35.

Storjohann, A.: Algorithms for Matrix Canonical Forms. Ph.D. thesis, Department of Computer Science, Swiss Federal Institute of Technology - ETH (2000)

36.

Tate, J.: Endomoprhisms of abelian varieties over finite fields. Inventiones Mathematica 2, 134–144 (1966)CrossRef

37.

Vélu, J.: Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A-B 273, A238–A241 (1971)

Titel: A Note on the Security of CSIDH
verfasst von: Jean-François Biasse
Annamaria Iezzi
Michael J. Jacobson Jr.
Verlag: Springer International Publishing
Buch: Progress in Cryptology – INDOCRYPT 2018
Print ISBN: 978-3-030-05377-2

Electronic ISBN: 978-3-030-05378-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-05378-9_9

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"