nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

CSIDH: An Efficient Post-Quantum Commutative Group Action

verfasst von : Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes

Erschienen in: Advances in Cryptology – ASIACRYPT 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 an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field \(\mathbb F_p\), rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

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 Towards Practical Key Exchange from Ordinary Isogeny Graphs

Nächstes Kapitel Computing Supersingular Isogenies on Kummer Surfaces

Since this work was started while being very close to a well-known large body of salt water, we pronounce CSIDH as

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-03332-3_15/475805_1_En_15_IEq19_HTML.gif

rather than spelling out all the letters.

This speed-up is explained in part by comparing our own C implementation to the sage implementation of De Feo–Kieffer–Smith.

This constraint only makes a difference for supersingular curves: in the ordinary case, all endomorphisms are defined over the base field.

Due to our convention of identifying k-isomorphic curves, we also identify isogenies if they are k-isomorphic, i.e., equal up to post-composition with a k-isomorphism.

This statement remains true in vast generality, but we only need this special case.

Note that the use of the word “ideal” is inconsistent in the literature. We make the convention that “ideal” without qualification refers to an integral \(\mathcal O\)-ideal (i.e., an ideal in the sense of ring theory), while fractional ideals are clearly named as such.

No pun intended.

The same idea gives rise to a simpler Monte Carlo algorithm which does not require the factorization of \(p+1\) but has a chance of false positives [64, Sect. 2.3].

The “square” SIDH counterparts of this protocol, as considered in [20, 30, 71], are not meaningful in the case of a commutative group action.

The min-entropy of a random variable is the negative logarithm of the probability of the most likely outcome.

Strictly speaking, the complexity depends on the size of the subset one samples private keys from, rather than the size of the class group, but as was argued before, these are approximately equal for our choice of m and n.

The page margins are certainly too narrow to contain such an analysis.

Here M and S denote a multiplication and squaring in \(\mathbb F_p\).

All our code is published in the public domain and is available for download at https://yx7.cc/code/csidh/csidh-latest.tar.xz.

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: SAC 2018 (2018)

Bernstein, D.J., van Gastel, B., Janssen, W., Lange, T., Schwabe, P., Smetsers, S.: TweetNaCl: a crypto library in 100 tweets. In: Aranha, D.F., Menezes, A. (eds.) LATINCRYPT 2014. LNCS, vol. 8895, pp. 64–83. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16295-9_4 CrossRefMATH

Biasse, J.-F., Iezzi, A., Jacobson Jr., M.J.: A note on the security of CSIDH (2018). https://arxiv.org/abs/1806.03656. To be published at Kangacrypt 2018

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_25 CrossRef

Bisson, G.: Computing endomorphism rings of elliptic curves under the GRH. J. Math. Cryptol. 5(2), 101–114 (2012)MathSciNetCrossRef

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

Brassard, G., Yung, M.: One-way group actions. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 94–107. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_7 CrossRef

Bröker, R.: A \(p\)-adic algorithm to compute the Hilbert class polynomial. Math. Comput. 77(264), 2417–2435 (2008)MathSciNetCrossRef

Bröker, R., Stevenhagen, P.: Efficient CM-constructions of elliptic curves over finite fields. Math. Comput. 76(260), 2161–2179 (2007)MathSciNetCrossRef

10.

Buchmann, J., Vollmer, U.: Binary Quadratic Forms: An Algorithmic Approach. Algorithms and Computation in Mathematics, vol. 20. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-46368-9 CrossRefMATH

11.

Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptol. 22(1), 93–113 (2009)MathSciNetCrossRef

12.

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

13.

Cohen, H., Lenstra Jr., 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)CrossRef

14.

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 CrossRef

15.

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 CrossRef

16.

Costello, C., Smith, B.: Montgomery curves and their arithmetic: the case of large characteristic fields. IACR Cryptology ePrint Archive 2017/212 (2017). https://ia.cr/2017/212

17.

Couveignes, J.-M.: Hard homogeneous spaces. IACR Cryptology ePrint Archive 2006/291 (2006). https://ia.cr/2006/291

18.

Cox, D.A.: Primes of the Form \(x^2+ny^2\): Fermat, Class Field Theory, and Complex Multiplication. Pure and Applied Mathematics, 2nd edn. Wiley, Hoboken (2013)CrossRef

19.

De Feo, L.: Mathematics of isogeny based cryptography (2017). https://arxiv.org/abs/1711.04062

20.

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

21.

De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Galbraith, S.D., Peyrin, T. (eds.) ASIACRYPT 2018, LNCS, vol. 11274, pp. xx–yy. Springer, Heidelberg (2018)

22.

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

23.

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

24.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12 CrossRef

25.

Freire, E.S.V., Hofheinz, D., Kiltz, E., Paterson, K.G.: Non-interactive key exchange. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 254–271. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_17 CrossRefMATH

26.

Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_34 CrossRef

27.

Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Computat. Math. 2, 118–138 (1999)MathSciNetCrossRef

28.

Galbraith, S.D.: Mathematics of Public-Key Cryptography. Cambridge University Press, Cambridge (2012)CrossRef

29.

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_3 CrossRef

30.

Galbraith, S.D., Petit, C., Silva, J.: Identification protocols and signature schemes based on supersingular isogeny problems. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 3–33. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_1 CrossRef

31.

Galbraith, S.D., Vercauteren, F.: Computational problems in supersingular elliptic curve isogenies. Quant. Inf. Process. 17. IACR Cryptology ePrint Archive 2017/774 (2018). https://ia.cr/2017/774

32.

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

33.

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

34.

Hallgren, S.: Fast quantum algorithms for computing the unit group and class group of a number field. In: STOC, pp. 468–474. ACM (2005)

35.

Hasse, H.: Zur Theorie der abstrakten elliptischen Funktionenkörper III. Die Struktur des Meromorphismenrings. Die Riemannsche Vermutung. J. für die reine und angewandte Mathematik 175, 193–208 (1936)

36.

Hofheinz, D., Hövelmanns, K., Kiltz, E.: A Modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12 CrossRefMATH

37.

Jao, D., Azarderakhsh, R., Campagna, M., Costello, C., De Feo, L., Hess, B., Jalali, A., Koziel, B., LaMacchia, B., Longa, P., Naehrig, M., Renes, J., Soukharev, V., Urbanik, D.: SIKE. Submission to [48]. http://sike.org

38.

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 CrossRefMATH

39.

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

40.

Jao, D., Miller, S.D., Venkatesan, R.: Expander graphs based on GRH with an application to elliptic curve cryptography. J. Number Theory 129(6), 1491–1504 (2009)MathSciNetCrossRef

41.

Kieffer, J.: Étude et accélération du protocole d’échange de clés de Couveignes-Rostovtsev-Stolbunov. Mémoire du Master 2, Université Paris VI (2017). https://arxiv.org/abs/1804.10128

42.

Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley (1996)

43.

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

44.

Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC, LIPIcs, vol. 22, pp. 20–34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

45.

Lenstra Jr., H.W., Lenstra, A.K., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)MathSciNetCrossRef

46.

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

47.

Mordell, L.J.: The congruence \((p-1/2)! \equiv \pm 1\ ({\rm mod}\ p)\). Am. Math. Mon. 68(2), 145–146 (1961)CrossRef

48.

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

49.

Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02295-1 CrossRefMATH

50.

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_12 CrossRef

51.

Pizer, A.K.: Ramanujan graphs and Hecke operators. Bull. Am. Math. Soc. (N.S.) 23(1), 127–137 (1990)MathSciNetCrossRef

52.

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

53.

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 CrossRef

54.

Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive 2006/145 (2006). https://ia.cr/2006/145

55.

Schoof, R.: Nonsingular plane cubic curves over finite fields. J. Comb. Theory Ser. A 46(2), 183–211 (1987)MathSciNetCrossRef

56.

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

57.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef

58.

Siegel, C.: Über die Classenzahl quadratischer Zahlkörper. Acta Arithmetica 1(1), 83–86 (1935)CrossRef

59.

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

60.

Stolbunov, A.: Public-key encryption based on cycles of isogenous elliptic curves. Master’s thesis, Saint-Petersburg State Polytechnical University (2004). (in Russian)

61.

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

62.

Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (2011)

63.

Sutherland, A.V.: Order computations in generic groups. Ph.D. thesis, Massachusetts Institute of Technology (2007). https://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf

64.

Sutherland, A.V.: Identifying supersingular elliptic curves. LMS J. Comput. Math. 15, 317–325 (2012)MathSciNetCrossRef

65.

Sutherland, A.V.: Isogeny volcanoes. In: ANTS X. Open Book Series, vol. 1, pp. 507–530. MSP (2012). https://arxiv.org/abs/1208.5370

66.

Tate, J.: Endomorphisms of abelian varieties over finite fields. Inventiones Mathematicae 2(2), 134–144 (1966)MathSciNetCrossRef

67.

The Sage Developers: SageMath, The Sage Mathematics Software System, Version 8.1 (2018). https://sagemath.org

68.

Unruh, D.: Quantum proofs of knowledge. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 135–152. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_10 CrossRef

69.

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

70.

Waterhouse, W.C.: Abelian varieties over finite fields. Annales scientifiques de l’École Normale Supérieure 2, 521–560 (1969)MathSciNetCrossRef

71.

Yoo, Y., Azarderakhsh, R., Jalali, A., Jao, D., Soukharev, V.: A post-quantum digital signature scheme based on supersingular isogenies. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 163–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_9 CrossRef

Titel: CSIDH: An Efficient Post-Quantum Commutative Group Action
verfasst von: Wouter Castryck
Tanja Lange
Chloe Martindale
Lorenz Panny
Joost Renes
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2018
Print ISBN: 978-3-030-03331-6

Electronic ISBN: 978-3-030-03332-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-03332-3_15

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"

Premium Partner