nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Quantum Security Analysis of CSIDH

verfasst von : Xavier Bonnetain, André Schrottenloher

Erschienen in: Advances in Cryptology – EUROCRYPT 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

CSIDH is a recent proposal for post-quantum non-interactive key-exchange, based on supersingular elliptic curve isogenies. It is similar in design to a previous scheme by Couveignes, Rostovtsev and Stolbunov, but aims at an improved balance between efficiency and security. In the proposal, the authors suggest concrete parameters in order to meet some desired levels of quantum security. These parameters are based on the hardness of recovering a hidden isogeny between two elliptic curves, using a quantum subexponential algorithm of Childs, Jao and Soukharev. This algorithm combines two building blocks: first, a quantum algorithm for recovering a hidden shift in a commutative group. Second, a computation in superposition of all isogenies originating from a given curve, which the algorithm calls as a black box.

In this paper, we give a comprehensive security analysis of CSIDH. Our first step is to revisit three quantum algorithms for the abelian hidden shift problem from the perspective of non-asymptotic cost, with trade-offs between their quantum and classical complexities. Second, we complete the non-asymptotic study of the black box in the hidden shift algorithm. We give a quantum procedure that evaluates CSIDH-512 using less than 40 000 logical qubits.

This allows us to show that the parameters proposed by the authors of CSIDH do not meet their expected quantum security.

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 He Gives C-Sieves on the CSIDH

Nächstes Kapitel Rational Isogenies from Irrational Endomorphisms

Unfortunately, CSIDH was published after the beginning of the NIST call, and it could not be submitted to the standardization process.

As in the end, we only need a list of size two, the bit we lose here is regained in the last step.

In classical time complexities, contrary to quantum time complexities, we dismiss the subset-sum polynomial factor, as we dismiss the cost of a single AES query, which is a standard approach.

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1–13 (1986). https://doi.org/10.1007/BF02579403MathSciNetCrossRefMATH

Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364–385. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_21CrossRef

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

Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 409–441. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_15CrossRef

Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FISh: efficient isogeny based signatures through class group computations. IACR Cryptology ePrint Archive 2019, 498 (2019). https://eprint.iacr.org/2019/498

Biasse, J.F., Fieker, C., Jacobson, 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., Iezzi, A., Jacobson, M.J.: A note on the security of CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 153–168. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_9CrossRef

Biasse, J.F., Bonnetain, X., Pring, B., Schrottenloher, A., Youmans, W.: A trade-off between classical and quantum circuit size for an attack against CSIDH. J. Math. Cryptol. (2020, to appear)

Bonnetain, X.: Improved low-qubit hidden shift algorithms. CoRR abs/1901.11428 (2019). http://arxiv.org/abs/1901.11428

10.

Bonnetain, X., Naya-Plasencia, M.: Hidden shift quantum cryptanalysis and implications. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11272, pp. 560–592. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_19CrossRef

11.

Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. IACR Cryptology ePrint Archive 2018, 537 (2018). https://eprint.iacr.org/2018/537

12.

Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15CrossRef

13.

Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptol. 22(1), 93–113 (2009). https://doi.org/10.1007/s00145-007-9002-xMathSciNetCrossRefMATH

14.

Cheung, K.K.H., Mosca, M.: Decomposing finite Abelian groups. Quantum Inf. Comput. 1(3), 26–32 (2001). http://portal.acm.org/citation.cfm?id=2011341MathSciNetMATH

15.

Chi, D.P., Kim, J.: Quantum database search by a single query. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol. 1509, pp. 148–151. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49208-9_11CrossRef

16.

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

17.

Cohen, H., Lenstra, H.W.: Heuristics on class groups of number fields. In: Jager, H. (ed.) Number Theory Noordwijkerhout 1983. LNM, vol. 1068, pp. 33–62. Springer, Heidelberg (1984). https://doi.org/10.1007/BFb0099440CrossRef

18.

Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291

19.

Dawson, C.M., Nielsen, M.A.: The Solovay-Kitaev algorithm. Quantum Inf. Comput. 6(1), 81–95 (2006)MathSciNetMATH

20.

De Feo, L., Galbraith, S.D.: SeaSign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 759–789. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_26CrossRef

21.

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

22.

Decru, T., Panny, L., Vercauteren, F.: Faster SeaSign signatures through improved rejection sampling. IACR Cryptology ePrint Archive 2018, 1109 (2018)

23.

Doulgerakis, E., Laarhoven, T., de Weger, B.: Finding closest lattice vectors using approximate Voronoi cells. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 3–22. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_1CrossRef

24.

Ettinger, M., Høyer, P.: On quantum algorithms for noncommutative hidden subgroups. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 478–487. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_45CrossRef

25.

Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 29–43. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29360-8_3CrossRefMATH

26.

Jalali, A., Azarderakhsh, R., Kermani, M.M., Jao, D.: Towards optimized and constant-time CSIDH on embedded devices. In: Polian, I., Stöttinger, M. (eds.) COSADE 2019. LNCS, vol. 11421, pp. 215–231. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16350-1_12CrossRef

27.

Jao, D., LeGrow, J., Leonardi, C., Ruiz-Lopez, L.: A subexponential-time, polynomial quantum space algorithm for inverting the CM group action. J. Math. Cryptol. (2018)

28.

Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. Electronic Colloquium on Computational Complexity (ECCC) 3(3) (1996)

29.

Kliuchnikov, V., Maslov, D., Mosca, M.: Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Inf. Comput. 13(7–8), 607–630 (2013)MathSciNet

30.

Knill, E.: An analysis of Bennett’s pebble game. CoRR abs/math/9508218 (1995)

31.

Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005)MathSciNetCrossRef

32.

Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, Guelph, Canada, 21–23 May 2013, pp. 20–34 (2013). https://doi.org/10.4230/LIPIcs.TQC.2013.20

33.

Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing AES as a quantum circuit. IACR Cryptology ePrint Archive 2019, 854 (2019)

34.

Levin, R.Y., Sherman, A.T.: A note on Bennett’s time-space tradeoff for reversible computation. SIAM J. Comput. 19(4), 673–677 (1990)MathSciNetCrossRef

35.

Meyer, M., Campos, F., Reith, S.: On Lions and Elligators: an efficient constant-time implementation of CSIDH. Cryptology ePrint Archive, Report 2018/1198 (2018). https://eprint.iacr.org/2018/1198

36.

Meyer, M., Reith, S.: A faster way to the CSIDH. In: Chakraborty, D., Iwata, T. (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 137–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_8CrossRef

37.

NIST: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

38.

Peikert, C.: He gives C-Sieves on the CSIDH. IACR Cryptology ePrint Archive 2019, 725 (2019)

39.

Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space. CoRR (2004). http://arxiv.org/abs/quant-ph/0406151

40.

Rines, R., Chuang, I.: High performance quantum modular multipliers. CoRR abs/1801.01081 (2018). http://arxiv.org/abs/1801.01081

41.

Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 241–270. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_9CrossRef

42.

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

43.

Schroeppel, R., Shamir, A.: A \({T} = {O}(2^{n/2})\), \({S} = {O}(2^{n/4})\) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456–464 (1981)

44.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, pp. 124–134. IEEE Computer Society (1994). https://doi.org/10.1109/SFCS.1994.365700

45.

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). https://doi.org/10.3934/amc.2010.4.215MathSciNetCrossRefMATH

46.

The Sage Developers: SageMath, the Sage Mathematics Software System. http://www.sagemath.org

Titel: Quantum Security Analysis of CSIDH
verfasst von: Xavier Bonnetain
André Schrottenloher
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2020
Print ISBN: 978-3-030-45723-5

Electronic ISBN: 978-3-030-45724-2

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-45724-2_17

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"