Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

SCALLOP-HD: Group Action from 2-Dimensional Isogenies

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2024 (PKC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14603))

Included in the following conference series:

Abstract

We present SCALLOP-HD, a novel group action that builds upon the recent SCALLOP group action introduced by De Feo, Fouotsa, Kutas, Leroux, Merz, Panny and Wesolowski in 2023. While our group action uses the same action of the class group \(\text {Cl}(\mathfrak {O})\) on \(\mathfrak {O}\)-oriented curves where \(\mathfrak {O}= \mathbb {Z}[f\sqrt{-d}]\) for a large prime f and small d as SCALLOP, we introduce a different orientation representation: The new representation embeds an endomorphism generating \(\mathfrak {O}\) in a \(2^e\)-isogeny between abelian varieties of dimension 2 with Kani’s Lemma, and this representation comes with a simple algorithm to compute the class group action. Our new approach considerably simplifies the SCALLOP framework, potentially surpassing it in efficiency—a claim supported by preliminary implementation results in SageMath. Additionally, our approach streamlines parameter selection. The new representation allows us to select efficiently a class group \(\text {Cl}(\mathfrak {O})\) of smooth order, enabling polynomial-time generation of the lattice of relation, hence enhancing scalability in contrast to SCALLOP.

To instantiate our SCALLOP-HD group action, we introduce a new technique to apply Kani’s Lemma in dimension 2 with an isogeny diamond obtained from commuting endomorphisms. This method allows one to represent arbitrary endomorphisms with isogenies in dimension 2, and may be of independent interest.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://yx7.cc/blah/2023-04-14.html.

  2. 2.

    We note that Kuperberg’s quantum algorithm works by first reducing to cyclic groups of two-power order, hence this group structure cannot be fundamentally weaker against Kuperberg’s algorithm than a random cyclic group of similar size. See for instance [Pan21, §2.6.3].

References

  1. Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 411–439. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_14

    Chapter  Google Scholar 

  2. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Open Book Ser. 4(1), 39–55 (2020)

    Article  MathSciNet  Google Scholar 

  3. Beullens, W., Dobson, S., Katsumata, S., Lai, Y.-F., Pintore, F.: Group signatures and more from isogenies and lattices: generic, simple, and efficient. Des Codes Cryptogr. 1–60 (2023)

    Google Scholar 

  4. Beullens, W., Katsumata, S., Pintore, F.: Calamari and Falafl: logarithmic (linkable) ring signatures from isogenies and lattices. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 464–492. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_16

    Chapter  Google Scholar 

  5. Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 227–247. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_9

    Chapter  Google Scholar 

  6. 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_15

    Chapter  Google Scholar 

  7. Basso, A., Maino, L., Pope, G.: FESTA: fast encryption from supersingular torsion attacks. Cryptology ePrint Archive (2023)

    Google Scholar 

  8. Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields, pp. 893–902 (2016)

    Google Scholar 

  9. Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 493–522. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_17

    Chapter  Google Scholar 

  10. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 423–447. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_15

  11. Castryck, W., Houben, M., Merz, S.P., Mula, M., Buuren, S.V., Vercauteren, F.: Weak instances of class group action based cryptography via self-pairings. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14083, pp. 762–792. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38548-3_25

    Chapter  Google Scholar 

  12. Chen, M., Imran, M., Ivanyos, G., Kutas, P., Leroux, A., Petit, C.: Hidden stabilizers, the isogeny to endomorphism ring problem and the cryptanalysis of pSIDH. Cryptology ePrint Archive, Paper 2023/779 (2023). https://eprint.iacr.org/2023/779

  13. Colò, L., Kohel, D.: Orienting supersingular isogeny graphs. J. Math. Cryptol. 14(1), 414–437 (2020)

    Article  MathSciNet  Google Scholar 

  14. 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_15

    Chapter  Google Scholar 

  15. Castryck, W., Panny, L., Vercauteren, F.: Rational isogenies from irrational endomorphisms. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 523–548. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_18

    Chapter  Google Scholar 

  16. Cozzo, D., Smart, N.P.: Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 169–186. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_10

    Chapter  Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. Castryck, W., Vercauteren, F.: A polynomial time attack on instances of M-SIDH and FESTA. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT. LNCS, vol. 14444, pp. 127–156. Springer, Heidelberg (2023). https://doi.org/10.1007/978-981-99-8739-9_5

    Chapter  Google Scholar 

  19. Feo, L.D., et al.: SCALLOP: scaling the CSI-FiSh. In: Boldyreva, A., Kolesnikov, V. (eds.) PKC. LNCS, vol. 13940, pp. 345–375. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-31368-4_13

    Chapter  Google Scholar 

  20. Feo, L.D., et al.: SCALLOP: scaling the CSI-FiSh. Cryptology ePrint Archive, Paper 2023/058 (2023). https://eprint.iacr.org/archive/2023/058/20230303:083840

  21. De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.: SQISign: compact post-quantum signatures from quaternions and isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 64–93. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_3

    Chapter  Google Scholar 

  22. De Feo, L., Leroux, A., Longa, P., Wesolowski, B.: New algorithms for the Deuring correspondence: towards practical and secure SQISign signatures. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 659–690. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_23

    Chapter  Google Scholar 

  23. De Feo, L., Meyer, M.: Threshold schemes from isogeny assumptions. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 187–212. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_7

    Chapter  Google Scholar 

  24. Dartois, P., Leroux, A., Robert, D., Wesolowski, B.: SQISignHD: new dimensions in cryptography. Cryptology ePrint Archive (2023)

    Google Scholar 

  25. Dartois, P., Maino, L., Pope, G., Robert, D.: An algorithmic approach to \((2,2)\)-isogenies in the theta model and applications to isogeny-based cryptography. IACR Cryptology ePrint Archive 2023/1747 (2023). https://eprint.iacr.org/2023/1747

  26. Decru, T., Maino, L., Sanso, A.: Towards a quantum-resistant weak verifiable delay function. Cryptology ePrint Archive (2023)

    Google Scholar 

  27. Eriksen, J.K., Panny, L., Sotáková, J., Veroni, M.: Deuring for the people: supersingular elliptic curves with prescribed endomorphism ring in general characteristic. In: LuCaNT 2023 (2023). https://eprint.iacr.org/2023/106

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

    Article  MathSciNet  Google Scholar 

  29. Herlédan Le Merdy, A., Wesolowski, B.: The supersingular endomorphism ring problem given one endomorphism. Cryptology ePrint Archive, Paper 2023/1448 (2023). https://eprint.iacr.org/2023/1448

  30. Kani, E.: The number of curves of genus two with elliptic differentials. J. für die reine und angewandte Mathematik (Crelles J.) 1997, 93–122 (1997)

    Article  MathSciNet  Google Scholar 

  31. Katsumata, S., Lai, Y.F., LeGrow, J.T., Qin, L.: CSI-Otter: Isogeny-based (partially) blind signatures from the class group action with a twist. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14083, pp. 729–761. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-38548-3_24

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

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  34. Leroux, A.: A new isogeny representation and applications to cryptography. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13792, pp. 3–35. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22966-4_1

    Chapter  Google Scholar 

  35. Leroux, A.: Quaternion Algebra and isogeny-based cryptography. PhD thesis, Ecole doctorale de l’Institut Polytechnique de Paris (2022)

    Google Scholar 

  36. Leroux, A.: Verifiable random function from the Deuring correspondence and higher dimensional isogenies. Cryptology ePrint Archive (2023)

    Google Scholar 

  37. Leroux, A., Roméas, M.: Updatable encryption from group actions. Cryptology ePrint Archive (2022)

    Google Scholar 

  38. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 448–471. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_16

    Chapter  Google Scholar 

  39. Onuki, H.: On oriented supersingular elliptic curves. Finite Fields App. 69 (2021)

    Google Scholar 

  40. Panny, L.: Cryptography on Isogeny Graphs. PhD thesis, Technische Universiteit Eindhoven (2021)

    Google Scholar 

  41. Peikert, C.: He gives C-Sieves on the CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 463–492. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_16

    Chapter  Google Scholar 

  42. Robert, D.: Evaluating isogenies in polylogarithmic time. Cryptology ePrint Archive (2022)

    Google Scholar 

  43. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 472–503. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_17

    Chapter  Google Scholar 

  44. The Sage Developers. SageMath, the Sage Mathematics Software System (version 10.2) (2023)

    Google Scholar 

  45. Waterhouse, W.C.: Abelian varieties over finite fields. In: Annales scientifiques de l’École normale supérieure, vol. 2, pp. 521–560 (1969)

    Google Scholar 

  46. Wesolowski, B.: Orientations and the supersingular endomorphism ring problem. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13277, pp. 345–371. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-07082-2_13

    Chapter  Google Scholar 

Download references

Acknowledgements

The first author would like to thank Christophe Petit for helpful feedback. Mingjie Chen is supported by EPSRC through grant number EP/V011324/1. Thanks to Giacomo Pope and Damien Robert for their help in debugging some corner cases of the 2-dimensional isogeny implementation.

Author information

Authors and Affiliations

  1. University of Birmingham, Birmingham, UK

    Mingjie Chen

  2. DGA-MI, Bruz, France

    Antonin Leroux

  3. IRMAR, UMR 6625, Université de Rennes, Rennes, France

    Antonin Leroux

  4. Technical University of Munich, Munich, Germany

    Lorenz Panny

  5. Université Libre de Bruxelles, Brussels, Belgium

    Mingjie Chen

Authors
  1. Mingjie Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonin Leroux
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lorenz Panny
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mingjie Chen .

Editor information

Editors and Affiliations

  1. The University of Sydney, Sydney, NSW, Australia

    Qiang Tang

  2. The Australian National University, Acton, ACT, Australia

    Vanessa Teague

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chen, M., Leroux, A., Panny, L. (2024). SCALLOP-HD: Group Action from 2-Dimensional Isogenies. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14603. Springer, Cham. https://doi.org/10.1007/978-3-031-57725-3_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-57725-3_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-57724-6

  • Online ISBN: 978-3-031-57725-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation