Skip to main content
Springer Nature Link
Log in

Supersingular Curves You Can Trust

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2023 (EUROCRYPT 2023)

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

Abstract

Generating a supersingular elliptic curve such that nobody knows its endomorphism ring is a notoriously hard task, despite several isogeny-based protocols relying on such an object. A trusted setup is often proposed as a workaround, but several aspects remain unclear. In this work, we develop the tools necessary to practically run such a distributed trusted-setup ceremony.

Our key contribution is the first statistically zero-knowledge proof of isogeny knowledge that is compatible with any base field. To prove statistical ZK, we introduce isogeny graphs with Borel level structure and prove they have the Ramanujan property. Then, we analyze the security of a distributed trusted-setup protocol based on our ZK proof in the simplified universal composability framework. Lastly, we develop an optimized implementation of the ZK proof, and we propose a strategy to concretely deploy the trusted-setup protocol.

Author list in alphabetical order; see https://ams.org/profession/leaders/CultureStatement04.pdf. This work began at the Banff International Research Station workshop “Supersingular Isogeny Graphs in Cryptography” (21w5229). This research was funded in part by the MIUR Excellence Department Project MatMod@TOV awarded to the Department of Mathematics, University of Rome Tor Vergata, the Commonwealth Cyber Initiative, the Academia Sinica Investigator Award AS-IA-109-M01, the Agence Nationale de la Recherche under grant ANR MELODIA (ANR-20-CE40-0013), and the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

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)
eBook
USD 84.99
Price excludes VAT (USA)
Softcover Book
USD 109.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The British spelling is Secure.

  2. 2.

    https://github.com/microsoft/PQCrypto-SIDH.

  3. 3.

    Deuring showed that any supersingular curve can be lifted in several ways to a curve with complex multiplication, but for almost all curves computing such lifts has complexity exponential in \(\log (p)\).

  4. 4.

    A function \(f:\mathbb {N}\rightarrow \mathbb {N}\) is said to be negligible in \(\lambda \) if for every positive polynomial p, \(f(\lambda )<1/p(\lambda )\) when \(\lambda \) is sufficiently large.

  5. 5.

    Rather than using the condition \(\phi (C_i)\subset C_j\), we could have defined \(\varLambda _{ij}\) using \(\phi (C_i)=C_j\). The second definition does not give a lattice but still permits to define a pairing. This second pairing generalizes to all level structures, so it might deserve better the name of Brandt pairing. However, the second pairing gives a more complicated proof in the Borel case, so we have opted for the first one.

  6. 6.

    The source code is available at https://github.com/trusted-isogenies/SECUER-pok.

  7. 7.

    https://github.com/microsoft/PQCrypto-SIDH.

References

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

    Chapter  Google Scholar 

  2. Alon, N., Benjamini, I., Lubetzky, E., Sodin, S.: Non-backtracking random walks mix faster. Commun. Contemp. Math. 9(4), 585–603 (2007). https://doi.org/10.1142/S0219199707002551

    Article  MathSciNet  MATH  Google Scholar 

  3. Arpin, S.: Adding level structure to supersingular elliptic curve isogeny graphs (2022). https://doi.org/10.48550/ARXIV.2203.03531, arXiv:2203.03531

  4. Basso, A.: A post-quantum round-optimal oblivious PRF from isogenies. Cryptology ePrint Archive, Paper 2023/225 (2023). https://eprint.iacr.org/2023/225

  5. Basso, A., et al.: Supersingular curves you can trust. Cryptology ePrint Archive, Report 2022/1469 (2022). https://eprint.iacr.org/2022/1469

  6. Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part I. LNCS, vol. 11476, pp. 103–128. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_4

    Chapter  Google Scholar 

  7. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Open Book Series 4(1), 39–55 (2020). https://doi.org/10.2140/obs.2020.4.39

    Article  MathSciNet  MATH  Google Scholar 

  8. 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, Part I. LNCS, vol. 11921, pp. 227–247. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_9

    Chapter  Google Scholar 

  9. Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 520–550. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_18

    Chapter  Google Scholar 

  10. Booher, J., et al.:: Failing to hash into supersingular isogeny graphs. Cryptology ePrint Archive, Report 2022/518 (2022). https://eprint.iacr.org/2022/518

  11. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12

  12. Burdges, J., De Feo, L.: Delay encryption. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 302–326. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-77870-5_11

  13. Canetti, R., Cohen, A., Lindell, Y.: A simpler variant of universally composable security for standard multiparty computation. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 3–22. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_1

  14. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Report 2022/975 (2022). https://eprint.iacr.org/2022/975

  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 III. LNCS, vol. 11274, pp. 395–427. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03332-3_15

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

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Chávez-Saab, J., Rodríguez-Henríquez, F., Tibouchi, M.: Verifiable isogeny walks: Towards an isogeny-based postquantum VDF. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 441–460. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-030-99277-4_21

  19. Cong, K., Lai, Y.F., Levin, S.: Efficient isogeny proofs using generic techniques. Cryptology ePrint Archive, Report 2023/037 (2023). https://eprint.iacr.org/2023/037

  20. Costello, C., Jao, D., Longa, P., Naehrig, M., Renes, J., Urbanik, D.: Efficient compression of SIDH public keys. In: Coron, J.S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part I. LNCS, vol. 10210, pp. 679–706. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-56620-7_24

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

  22. De Feo, L., et al.: Séta: Supersingular encryption from torsion attacks. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part IV. LNCS, vol. 13093, pp. 249–278. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-92068-5_9

  23. De Feo, L., Dobson, S., Galbraith, S.D., Zobernig, L.: SIDH proof of knowledge. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part II. LNCS, vol. 13792, pp. 310–339. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22966-4_11

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

  25. 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). https://doi.org/10.1515/jmc-2012-0015

    Article  MathSciNet  MATH  Google Scholar 

  26. De Feo, L., Kieffer, J., Smith, B.: Towards practical key exchange from ordinary isogeny graphs. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part III. LNCS, vol. 11274, pp. 365–394. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03332-3_14

  27. 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, Part I. LNCS, vol. 12491, pp. 64–93. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64837-4_3

  28. De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 248–277. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34578-5_10

  29. Decru, T., Panny, L., Vercauteren, F.: Faster SeaSign signatures through improved rejection sampling. In: Ding, J., Steinwandt, R. (eds.) Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019. pp. 271–285. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-25510-7_15

  30. Deligne, P.: La conjecture de Weil : I. Publications Mathématiques de l’IHÉS 43, 273–307 (1974). http://www.numdam.org/item/PMIHES_1974__43__273_0/

  31. Diamond, F., Shurman, J.: A First Course in Modular Forms, Graduate Texts in Mathematics, vol. 228. Springer-Verlag, New York (2005). https://doi.org/10.1007/978-0-387-27226-9

  32. Eisenträger, K., Hallgren, S., Lauter, K.E., Morrison, T., Petit, C.: Supersingular isogeny graphs and endomorphism rings: reductions and solutions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 329–368. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-78372-7_11

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

  34. Fouotsa, T.B., Kutas, P., Merz, S.P., Ti, Y.B.: On the isogeny problem with torsion point information. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022, Part I. LNCS, vol. 13177, pp. 142–161. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-030-97121-2_6

  35. 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, Part I. LNCS, vol. 10031, pp. 63–91. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_3

  36. 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, Part I. LNCS, vol. 10624, pp. 3–33. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-70694-8_1

  37. Galbraith, S.D., Petit, C., Silva, J.: Identification protocols and signature schemes based on supersingular isogeny problems. J. Cryptol. 33(1), 130–175 (2019). https://doi.org/10.1007/s00145-019-09316-0

    Article  MathSciNet  MATH  Google Scholar 

  38. Ghantous, W., Pintore, F., Veroni, M.: Collisions in supersingular isogeny graphs and the SIDH-based identification protocol. Cryptology ePrint Archive, Report 2021/1051 (2021). https://eprint.iacr.org/2021/1051

  39. Goren, E.Z., Kassaei, P.L.: \(p\)-adic dynamics of Hecke operators on modular curves. Journal de Théorie des Nombres de Bordeaux 33(2), 387–431 (2021). https://www.jstor.org/stable/48618785

  40. Hijikata, H., Pizer, A.K., Shemanske, T.R.: The basis problem for modular forms on \({\Gamma }_{0}(N)\). Mem. Amer. Math. Soc. 82(418), vi+159 (1989). https://doi.org/10.1090/memo/0418

  41. Jao, D., et al.: SIKE. Tech. rep., National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions

  42. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011. pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2

  43. Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkley (1996). https://www.i2m.univ-amu.fr/perso/david.kohel/pub/thesis.pdf

  44. Lai, Y.F., Galbraith, S.D., de Saint Guilhem, C.: Compact, efficient and UC-secure isogeny-based oblivious transfer. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 213–241. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-77870-5_8

  45. Love, J., Boneh, D.: Supersingular curves with small noninteger endomorphisms. Open Book Series 4(1), 7–22 (2020). https://doi.org/10.2140/obs.2020.4.7

    Article  MathSciNet  MATH  Google Scholar 

  46. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: To appear in EUROCRYPT 2023. LNCS, Springer, Heidelberg (2023). https://eprint.iacr.org/2022/1026

  47. Mestre, J.F.: La méthode des graphes. Exemples et applications. In: Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986). Nagoya University, Nagoya (1986). https://wstein.org/msri06/refs/mestre-method-of-graphs/mestre-fr.pdf

  48. Mula, M., Murru, N., Pintore, F.: Random sampling of supersingular elliptic curves. Cryptology ePrint Archive, Report 2022/528 (2022). https://eprint.iacr.org/2022/528

  49. Petit, C.: Faster algorithms for isogeny problems using torsion point images. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 330–353. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-70697-9_12

  50. Pizer, A.K.: Ramanujan graphs and Hecke operators. Bulletin of the American Mathematical Society (N.S.) 23(1) (1990). https://doi.org/10.1090/S0273-0979-1990-15918-X

  51. de Quehen, V., et al.: Improved torsion-point attacks on SIDH variants. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part III. LNCS, vol. 12827, pp. 432–470. Springer, Heidelberg, Virtual Event (2021). https://doi.org/10.1007/978-3-030-84252-9_15

  52. Robert, D.: Breaking SIDH in polynomial time. Cryptology ePrint Archive, Report 2022/1038 (2022). https://eprint.iacr.org/2022/1038

  53. Schoeneberg, B.: Elliptic modular functions: an introduction. Die Grundlehren der mathematischen Wissenschaften, Band 203, Springer, Heidelberg (1974). https://doi.org/10.1007/978-3-642-65663-7

  54. Sterner, B.: Commitment schemes from supersingular elliptic curve isogeny graphs. Math. Cryptol. 1(2), 40–51 (2022). https://journals.flvc.org/mathcryptology/article/view/130656

  55. 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.215

    Article  MathSciNet  MATH  Google Scholar 

  56. Vélu, J.: Isogénies entre courbes elliptiques. CR Acad. Sci. Paris, Séries A 273, 305–347 (1971)

    Google Scholar 

  57. Voight, J.: Quaternion algebras, Graduate Texts in Mathematics, vol. 288. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-56694-4

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

  59. Wesolowski, B.: The supersingular isogeny path and endomorphism ring problems are equivalent. In: 62nd FOCS. pp. 1100–1111. IEEE Computer Society Press (2022). https://doi.org/10.1109/FOCS52979.2021.00109

Download references

Acknowledgments

We are grateful to the reviewers and to Shai Levin for helping catch several mistakes and misprints. We thank Jeff Burdges for valuable discussions during the preparation of this work.

Author information

Authors and Affiliations

  1. University of Birmingham, Birmingham, UK

    Andrea Basso

  2. University of Bristol, Bristol, UK

    Andrea Basso

  3. Dipartimento di Matematica, Università degli Studi di Roma Tor Vergata, Via della Ricerca Scientifica, 00133, Roma, Italy

    Giulio Codogni & Guido Maria Lido

  4. Zcash Foundation, Mclean, USA

    Deirdre Connolly

  5. IBM Research Europe, Zürich, Switzerland

    Luca De Feo

  6. EPFL, Lausanne, Switzerland

    Tako Boris Fouotsa

  7. Virginia Tech, Blacksburg, VA, USA

    Travis Morrison

  8. Academia Sinica, Taipei, Taiwan

    Lorenz Panny

  9. IBM Research India, Bangalore, India

    Sikhar Patranabis

  10. Univ. Bordeaux, CNRS, Bordeaux INP, IMB, UMR 5251, 33400, Talence, France

    Benjamin Wesolowski

  11. INRIA, IMB, UMR 5251, 33400, Talence, France

    Benjamin Wesolowski

  12. ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

    Benjamin Wesolowski

Authors
  1. Andrea Basso
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giulio Codogni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Deirdre Connolly
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luca De Feo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tako Boris Fouotsa
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Guido Maria Lido
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Travis Morrison
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Lorenz Panny
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Sikhar Patranabis
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Benjamin Wesolowski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea Basso .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Basso, A. et al. (2023). Supersingular Curves You Can Trust. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14005. Springer, Cham. https://doi.org/10.1007/978-3-031-30617-4_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30617-4_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30616-7

  • Online ISBN: 978-3-031-30617-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation