research-article

Open access

SoK: The Problem Landscape of SIDH

Authors:

David JaoAuthors Info & Claims

APKC '18: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop

Pages 53 - 60

https://doi.org/10.1145/3197507.3197516

Published: 23 May 2018 Publication History

Abstract

The Supersingular Isogeny Diffie-Hellman protocol (SIDH) has recently been the subject of increased attention in the cryptography community. Conjecturally quantum-resistant, SIDH has the feature that it shares the same data flow as ordinary Diffie-Hellman: two parties exchange a pair of public keys, each generated from a private key, and combine them to form a shared secret. To create a potentially quantum-resistant scheme, SIDH depends on a new family of computational assumptions involving isogenies between supersingular elliptic curves which replace both the discrete logarithm problem and the computational and decisional Diffie-Hellman problems. As in the case of ordinary Diffie-Hellman, one is interested in knowing if these problems are related. In fact, more is true: there is a rich network of reductions between the isogeny problems securing the private keys of the participants in the SIDH protocol, the computational and decisional SIDH problems, and the problem of validating SIDH public keys. In this article we explain these relationships, which do not appear elsewhere in the literature, in hopes of providing a clearer picture of the SIDH problem landscape to the cryptography community at large.

References

[1]

Jean-François Biasse, David Jao, and Anirudh Sankar. 2014. A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves. In Progress in Cryptology - INDOCRYPT 2014: 15th International Conference on Cryptology in India, New Delhi, India, December 14--17, 2014, Proceedings, Willi Meier and Debdeep Mukhopadhyay (Eds.). Springer International Publishing, Cham, 428-- 442.

[2]

Andrew Childs, David Jao, and Vladimir Soukharev. 2014. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology 8, 1 (2014), 1--29.

[3]

Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes, and David Urbanik. 2017. Efficient Compression of SIDH Public Keys. In Advances in Cryptology - EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 -- May 4, 2017, Proceedings, Part I, Jean-Sébastien Coron and Jesper Buus Nielsen (Eds.). Springer International Publishing, Cham, 679--706.

[4]

Craig Costello, Patrick Longa, and Michael Naehrig. 2016. Efficient Algorithms for Supersingular Isogeny Diffie-Hellman. In Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14--18, 2016, Proceedings, Part I, Matthew Robshaw and Jonathan Katz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 572--601.

Digital Library

[5]

Christina Delfs and Steven D. Galbraith. 2016. Computing isogenies between supersingular elliptic curves over Fp . Designs, Codes and Cryptography 78, 2 (01 Feb 2016), 425--440.

Digital Library

[6]

Steven D. Galbraith. 1999. Constructing Isogenies between Elliptic Curves Over Finite Fields. LMS Journal of Computation and Mathematics 2 (1999), 118--138.

[7]

Steven D. Galbraith, Christophe Petit, Barak Shani, and Yan Bo Ti. 2016. On the Security of Supersingular Isogeny Cryptosystems. In Advances in Cryptology - ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4--8, 2016, Proceedings, Part I, Jung Hee Cheon and Tsuyoshi Takagi (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 63--91.

[8]

Steven D. Galbraith, Christophe Petit, and Javier Silva. 2017. Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems. In Advances in Cryptology - ASIACRYPT 2017, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, Cham, 3--33.

[9]

Steven D. Galbraith and Frederik Vercauteren. 2017. Computational problems in supersingular elliptic curve isogenies. Cryptology ePrint Archive, Report 2017/774. (2017). https://eprint.iacr.org/2017/774.

[10]

Shafi Goldwasser and Silvio Micali. 1984. Probabilistic encryption. J. Comput. System Sci. 28, 2 (1984), 270 -- 299.

[11]

David Jao and Luca De Feo. 2011. Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In Post-Quantum Cryptography, Bo-Yin Yang (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 19--34.

Digital Library

[12]

David Jao and Vladimir Soukharev. 2014. Isogeny-Based Quantum-Resistant Undeniable Signatures. In Post-Quantum Cryptography: 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1--3, 2014. Proceedings, Mosca, Michele (Ed.). Springer International Publishing, Cham, 160--179.

[13]

Daniel Kirkwood, Bradley C. Lackey, John McVey, Mark Motley, Jerome A. Solinas, and David Tuller. April, 2015. Failure is not an Option: Standardization issues for post-quantum key agreement. Talk at NIST workshop on Cybersecurity in a Post-Quantum World: http://www.nist.gov/itl/csd/ct/ post-quantum-crypto-workshop-2015.cfm. (April, 2015).

[14]

Victor S. Miller. 2004. The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology 17, 4 (01 Sep 2004), 235--261.

Digital Library

[15]

Christophe Petit. 2017. Faster Algorithms for Isogeny Problems Using Torsion Point Images. In Advances in Cryptology - ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3--7, 2017, Proceedings, Part II, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, Cham, 330--353.

[16]

Stephen Pohlig and Martin Hellman. 1978. An improved algorithm for computing logarithms over GF (p) and its cryptographic significance (Corresp.). IEEE Transactions on Information Theory 24, 1 (January 1978), 106--110.

Digital Library

[17]

Joseph Silverman. 2009. The Arithmetic of Elliptic Curves (2nd ed.). Graduate Texts in Mathematics, Vol. 106. Springer-Verlag, New York.

[18]

Xi Sun, Haibo Tian, and Yumin Wang. 2012. Toward Quantum-Resistant Strong Designated Verifier Signature from Isogenies. In 2012 Fourth International Conference on Intelligent Networking and Collaborative Systems. 292--296.

Digital Library

[19]

Erik Thormarker. 2017. Post-Quantum Cryptography: Supersingular Isogeny DiffieHellman Key Exchange. Master's thesis. Stockholm University. http://kurser.math. su.se/pluginfile.php/16103/mod_folder/content/0/2017/2017_42_report.pdf.

[20]

Jacques Vélu. 1971. Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238--A241.

[21]

Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao, and Vladimir Soukharev. 2017. A Post-quantum Digital Signature Scheme Based on Supersingular Isogenies. In Financial Cryptography and Data Security, Aggelos Kiayias (Ed.). Springer International Publishing, Cham, 163--181.

Cited By

Robert D(2025)On the Efficient Representation of IsogeniesNumber-Theoretic Methods in Cryptology10.1007/978-3-031-82380-0_1(3-84)Online publication date: 19-Feb-2025
https://doi.org/10.1007/978-3-031-82380-0_1
Castryck WVercauteren F(2023)A Polynomial Time Attack on Instances of M-SIDH and FESTAAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_5(127-156)Online publication date: 18-Dec-2023
https://doi.org/10.1007/978-981-99-8739-9_5
Castryck WDecru T(2023)An Efficient Key Recovery Attack on SIDHAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30589-4_15(423-447)Online publication date: 16-Apr-2023
https://doi.org/10.1007/978-3-031-30589-4_15
Show More Cited By

Index Terms

SoK: The Problem Landscape of SIDH
1. Security and privacy
  1. Cryptography
    1. Cryptanalysis and other attacks
    2. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Efficient Algorithms for Supersingular Isogeny Diffie-Hellman
Proceedings, Part I, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 9814

We propose a new suite of algorithms that significantly improve the performance of supersingular isogeny Diffie-Hellman SIDH key exchange. Subsequently, we present a full-fledged implementation of SIDH that is geared towards the 128-bit quantum and 192-...
Optimized Arithmetic Operations for Isogeny-Based Cryptography on Huff Curves
Information Security and Privacy
Abstract
Up to now, the state-of-the-art implementations of Supersingular Isogeny Diffie-Hellman (SIDH) work with Montgomery curves or Edwards curves, due to the facts that such curve models provide high efficiency for elliptic curve arithmetic operations. ...
Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves
Advances in Cryptology – ASIACRYPT 2019
Abstract
In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the w-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

APKC '18: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop

May 2018

66 pages

ISBN:9781450357562

DOI:10.1145/3197507

Program Chairs:
Keita Emura
National Institute of Information & Communications Technology, Japan
,
Jae Hong Seo
Hanyang University, Korea
,
Yohei Watanabe
The University of Electro-Communications, Japan

Copyright © 2018 Owner/Author.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs International 4.0 License.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Public Works and Government Services Canada
Royal Bank of Canada
Natural Sciences and Engineering Research Council of Canada

Conference

ASIA CCS '18

Sponsor:

SIGSAC

ASIA CCS '18: ACM Asia Conference on Computer and Communications Security

June 4, 2018

Incheon, Republic of Korea

Acceptance Rates

APKC '18 Paper Acceptance Rate 7 of 20 submissions, 35%;

Overall Acceptance Rate 36 of 103 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
510
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)24

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Robert D(2025)On the Efficient Representation of IsogeniesNumber-Theoretic Methods in Cryptology10.1007/978-3-031-82380-0_1(3-84)Online publication date: 19-Feb-2025
https://doi.org/10.1007/978-3-031-82380-0_1
Castryck WVercauteren F(2023)A Polynomial Time Attack on Instances of M-SIDH and FESTAAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_5(127-156)Online publication date: 18-Dec-2023
https://doi.org/10.1007/978-981-99-8739-9_5
Castryck WDecru T(2023)An Efficient Key Recovery Attack on SIDHAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30589-4_15(423-447)Online publication date: 16-Apr-2023
https://doi.org/10.1007/978-3-031-30589-4_15
Prabowo TTan C(2023)Provably Secure Password-Authenticated Key Exchange Based on SIDHInformation Security Applications10.1007/978-3-031-25659-2_2(16-28)Online publication date: 4-Feb-2023
https://doi.org/10.1007/978-3-031-25659-2_2
Beegala PRoy DRavi PBhasin SChattopadhyay AMukhopadhyay D(2022)Efficient Loop Abort Fault Attacks on Supersingular Isogeny based Key Exchange (SIKE)2022 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)10.1109/DFT56152.2022.9962359(1-6)Online publication date: 19-Oct-2022
https://doi.org/10.1109/DFT56152.2022.9962359
De Feo LDobson SGalbraith SZobernig L(2022)SIDH Proof of KnowledgeAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22966-4_11(310-339)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22966-4_11
Schwenk JSchwenk J(2022)Cryptography: ConfidentialityGuide to Internet Cryptography10.1007/978-3-031-19439-9_2(13-41)Online publication date: 26-Nov-2022
https://doi.org/10.1007/978-3-031-19439-9_2
Grebnev S(2020)Limonnitsa: making Limonnik-3 post-quantumМатематические вопросы криптографииMatematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]10.4213/mvk31911:2(25-42)Online publication date: 2-Dec-2020
https://doi.org/10.4213/mvk319
Biasse JPring B(2020)A framework for reducing the overhead of the quantum oracle for use with Grover’s algorithm with applications to cryptanalysis of SIKEJournal of Mathematical Cryptology10.1515/jmc-2020-008015:1(143-156)Online publication date: 17-Nov-2020
https://doi.org/10.1515/jmc-2020-0080
de Saint Guilhem COrsini EPetit CSmart N(2020)Semi-commutative Masking: A Framework for Isogeny-Based Protocols, with an Application to Fully Secure Two-Round Isogeny-Based OTCryptology and Network Security10.1007/978-3-030-65411-5_12(235-258)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65411-5_12
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten