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

CSIDH on the Surface

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2020)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12100))

Included in the following conference series:

Abstract

For primes \(p \equiv 3 \bmod 4\), we show that setting up CSIDH on the surface, i.e., using supersingular elliptic curves with endomorphism ring \(\mathbf {Z}[(1 + \sqrt{-p})/2]\), amounts to just a few sign switches in the underlying arithmetic. If \(p \equiv 7 \bmod 8\) then horizontal 2-isogenies can be used to help compute the class group action. The formulas we derive for these 2-isogenies are very efficient (they basically amount to a single exponentiation in \(\mathbf {F}_p\)) and allow for a noticeable speed-up, e.g., our resulting CSURF-512 protocol runs about \(5.68\%\) faster than CSIDH-512. This improvement is completely orthogonal to all previous speed-ups, constant-time measures and construction of cryptographic primitives that have appeared in the literature so far. At the same time, moving to the surface gets rid of the redundant factor \(\mathbf {Z}_3\) of the acting ideal-class group, which is present in the case of CSIDH and offers no extra security.

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 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.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.

    Moreover, if \(p \equiv 3 \bmod 4\) then \(x^3 + Ax^2 - x\) is automatically square-free, allowing for a marginally simpler key validation. But this deserves a footnote, at most.

  2. 2.

    It has been pointed out, e.g. in [8, 17], that allowing for the action of \((4, \sqrt{-p} - 1)\) could lead to a minor improvement. See also Remark 2.

References

  1. Baelen, B.: Post-quantum key-exchange: using group actions from supersingular elliptic curve isogenies. Master’s thesis, KU Leuven (2019)

    Google Scholar 

  2. Bernstein, D.J., Lange, T.: Montgomery curves and the Montgomery ladder. In: Bos, J.W., Lenstra, A.K. (eds.) Topics in Computational Number Theory Inspired by Peter L. Montgomery, pp. 82–115. Cambridge University Press, Cambridge (2017)

    Chapter  Google Scholar 

  3. 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. Part II. LNCS, vol. 11477, pp. 409–441. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_15

    Chapter  Google Scholar 

  4. 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 

  5. Bonnetain, X., Schrottenloher, A.: Submerging CSIDH. IACR Cryptology ePrint Archive, p. 537 (2018)

    Google Scholar 

  6. Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I. The user language. J. Symbolic Comput. 24(3–4), 235–265 (1997). Computational algebra and number theory (London, 1993)

    Article  MathSciNet  Google Scholar 

  7. 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, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15

    Chapter  Google Scholar 

  8. Castryck, W., Panny, L., Vercauteren, F.: Rational isogenies from irrational endomorphisms. IACR Cryptology ePrint Archive, 2019:1202 (2019)

    Google Scholar 

  9. 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

    Chapter  Google Scholar 

  10. Couveignes, J.-M.: Hard homogeneous spaces. IACR Cryptology ePrint Archive, 2006:291 (2006)

    Google Scholar 

  11. De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. IACR Cryptology ePrint Archive, 2019:166 (2019)

    Google Scholar 

  12. De Feo, L., Meyer, M.: Threshold schemes from isogeny assumptions. IACR Cryptology ePrint Archive, 2019:1288 (2019)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Fan, X., Tian, S., Li, B., Xiu, X.: CSIDH on other form of elliptic curves. IACR Cryptology ePrint Archive, 2019:1417 (2019)

    Google Scholar 

  15. Hutchinson, A., LeGrow, J., Koziel, B., Azarderakhsh, R.: Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors. IACR Cryptology ePrint Archive, 2019:1121 (2019)

    Google Scholar 

  16. 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. LIPIcs, Leibniz International Proceedings in Informatics, vol. 22, pp. 20–34 (2013)

    Google Scholar 

  17. Onuki, H., Takagi, T.: On collisions related to an ideal class of order 3 in CSIDH. IACR Cryptology ePrint Archive, 2019:1209 (2019)

    Google Scholar 

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

    Google Scholar 

  19. 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

    Chapter  Google Scholar 

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

    Google Scholar 

  21. Schoof, R.: Nonsingular plane cubic curves over finite fields. J. Combin. Theor. Ser. A 46(2), 183–211 (1987)

    Article  MathSciNet  Google Scholar 

  22. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Cosic, Research Group at Imec and KU Leuven, Leuven, Belgium

    Wouter Castryck & Thomas Decru

Authors
  1. Wouter Castryck
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Decru
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Decru .

Editor information

Editors and Affiliations

  1. University of Cincinnati, Cincinnati, OH, USA

    Jintai Ding

  2. Inria, Paris, France

    Jean-Pierre Tillich

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Castryck, W., Decru, T. (2020). CSIDH on the Surface. In: Ding, J., Tillich, JP. (eds) Post-Quantum Cryptography. PQCrypto 2020. Lecture Notes in Computer Science(), vol 12100. Springer, Cham. https://doi.org/10.1007/978-3-030-44223-1_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-44223-1_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-44222-4

  • Online ISBN: 978-3-030-44223-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation