Abstract
In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order \(\mathcal {O}\). We prove that the order m of such a self-pairing necessarily satisfies \(m \mid \varDelta _\mathcal {O}\) (and even \(2m \mid \varDelta _\mathcal {O}\) if \(4 \mid \varDelta _\mathcal {O}\) and \(4m \mid \varDelta _\mathcal {O}\) if \(8 \mid \varDelta _\mathcal {O}\)) and is not a multiple of the field characteristic. Conversely, for each m satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order m that are compatible with oriented isogenies, based on generalized Weil and Tate pairings.
As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if \(m^2 \mid \varDelta _\mathcal {O}\) for some prime power m then given two primitively \(\mathcal {O}\)-oriented elliptic curves \((E, \iota )\) and \((E',\iota ') = [\mathfrak {a}](E,\iota )\) connected by an unknown invertible ideal \(\mathfrak {a}\subseteq \mathcal {O}\), we can recover \(\mathfrak {a}\) essentially at the cost of a discrete logarithm computation in a group of order \(m^2\), assuming the norm of \(\mathfrak {a}\) is given and is smaller than \(m^2\). We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack.
Finally, we show that these self-pairings simplify known results on the decisional Diffie–Hellman problem for class group actions on oriented elliptic curves.
This work was supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ISOCRYPT - No. 101020788) and by CyberSecurity Research Flanders with reference number VR20192203.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
It may seem suspicious, at first sight, that \(f_{m,P}(D_Q)\) does not depend on \(\psi \). However, here too, the Frey–Rück \(\psi \)-Tate pairing is just a restriction of the Frey–Rück m-Tate pairing.
- 2.
For instance, to allow for \(\sigma \) of the form \((\pi _q - 1)/b\) as in Example 5.2.
- 3.
The reduction was presented at the KU Leuven isogeny days in 2022 and an article about this is in preparation [17].
- 4.
See https://github.com/KULeuven-COSIC/Weak-Class-Group-Actions for the code.
- 5.
If \({{\,\textrm{char}\,}}(k) = 2\) then it seems like we may be missing more than one assigned character, but see [7, Footnote 1] for why this is not the case.
References
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: the user language. J. Symb. Comput. 24(3–4), 235–265 (1997)
Bruin, P.: The Tate pairing for Abelian varieties over finite fields. Journal de Théorie des Nombres de Bordeaux 23(2), 323–328 (2011)
Castryck, W., Decru, T.: CSIDH on the surface. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 111–129. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_7
Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) Eurocrypt 2023 Part 5. LNCS, vol. 14008, pp. 423–447. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30589-4_15
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 Part 3. LNCS, vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15
Castryck, W., Sotáková, J., Vercauteren, F.: Breaking the decisional Diffie-Hellman problem for class group actions using Genus theory. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020 Part 2. LNCS, vol. 12171, pp. 92–120. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_4
Castryck, W., Houben, M., Vercauteren, F., Wesolowski, B.: On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves. Res. Number Theory 8(4), 99 (2022)
Castryck, W., Houben, M., Merz, S.-P., Mula, M., van Buuren, S., Vercauteren, F.: Weak instances of class group action based cryptography via self-pairings (2023). Full version on ePrint Archive available at https://eprint.iacr.org/2023/549
Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.-J., De Feo, L., Rodríguez-Henríquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 173–193. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_9
Chávez-Saab, J., Chi-Domínguez, J.-J., Jaques, S., Rodríguez-Henríquez, F.: The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents. J. Cryptogr. Eng. 12(3), 349–368 (2022)
Chenu, M., Smith, B.: Higher-degree supersingular group actions. Math. Cryptol. 1(2), 85–101 (2021)
Colò, L., Kohel, D.: Orienting supersingular isogeny graphs. J. Math. Cryptol. 14(1), 414–437 (2020)
Couveignes, J.-M.: Hard homogeneous spaces (2006). Unpublished article. https://eprint.iacr.org/2006/291
Cox, D.A.: Primes of the Form \(x^2+ny^2\): Fermat, Class Field Theory, and Complex Multiplication, vol. 116. Pure and Applied Mathematics, 2nd edn. Wiley (2013)
Dartois, P., De Feo, L.: On the security of OSIDH. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022 Part 1. LNCS, vol. 13177, pp. 52–81. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97121-2_3
De Feo, L., et al.: SCALLOP: scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023 Part 1. LNCS, vol. 13940, pp. 345–375. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-31368-4_13
De Feo, L., et al.: Modular isogeny problems. Private communication
Frey, G., Rück, H.-G.: A remark concerning \(m\)-divisibility and the discrete logarithm in class groups of curves. Math. Comput. 62, 865–874 (1994)
Galbraith, S.: Pairings. In: Blake, I.F., Seroussi, G., Smart, N.P. (eds.) Advances in Elliptic Curve Cryptography. LMS Lecture Note Series, Chapter 9, vol. 317, pp. 183–213. Cambridge University Press (2005)
Garefalakis, T.: The generalized Weil pairing and the discrete logarithm problem on elliptic curves. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 118–130. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45995-2_15
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
Lenstra, H.W.: Complex multiplication structure of elliptic curves. J. Number Theory 56, 227–241 (1996)
Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Eurocrypt 2023 Part 5. LNCS, vol. 14008, pp. 448–471. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30589-4_16
Miller, V.S.: Short programs for functions on curves (1986). Unpublished note https://crypto.stanford.edu/miller/miller.pdf
Miller, V.S.: The Weil pairing, and its efficient calculation. J. Cryptol. 17(4), 235–261 (2004)
Moriya, Tomoki, Onuki, Hiroshi, Takagi, Tsuyoshi: SiGamal: a supersingular isogeny-based PKE and its application to a PRF. In: Moriai, Shiho, Wang, Huaxiong (eds.) ASIACRYPT 2020 Part 2. LNCS, vol. 12492, pp. 551–580. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_19
Onuki, H.: On oriented supersingular elliptic curves. Finite Fields Appl. 69, Article id 101777 (2021)
Robert, D.: Efficient algorithms for Abelian varieties and their moduli spaces. Habilitation à Diriger des Recherches (2021)
Robert, D.: Some applications of higher dimensional isogenies to elliptic curves (overview of results) (2022). Preprint https://eprint.iacr.org/2022/1704
Robert, D.: The geometric interpretation of the Tate pairing and its applications (2023). Preprint https://eprint.iacr.org/2023/177
Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) Eurocrypt 2023 Part 5. LNCS, vol. 14008, pp. 472–503. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30589-4_17
Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies (2006). Unpublished article https://eprint.iacr.org/2006/145
Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Mathematici Universitatis Sancti Pauli 47, 81–92 (1998)
Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod \(p\). Math. Comput. 44(170), 483–494 (1985)
Schoof, R.: Nonsingular plane cubic curves over finite fields. J. Comb. Theory Ser. A 36(2), 183–211 (1987)
Silverman, J.H.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106, 2nd edn. Springer, Cham (2009). https://doi.org/10.1007/978-0-387-09494-6
Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12, 193–196 (1999)
Waterhouse, W.C.: Abelian varieties over finite fields. Annales scientifiques de l’École Normale Supérieure 2, 521–560 (1969)
Wesolowski, B.: The supersingular isogeny path and endomorphism ring problems are equivalent. In: FOCS 2021, pp. 1100–1111. IEEE (2022)
Acknowledgements
We owe thanks to Luca De Feo, Damien Robert, Katherine Stange and the anonymous reviewers for various helpful comments, discussions and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Castryck, W., Houben, M., Merz, SP., Mula, M., Buuren, S.v., Vercauteren, F. (2023). Weak Instances of Class Group Action Based Cryptography via Self-pairings. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14083. Springer, Cham. https://doi.org/10.1007/978-3-031-38548-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-38548-3_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-38547-6
Online ISBN: 978-3-031-38548-3
eBook Packages: Computer ScienceComputer Science (R0)
