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-bit classical security levels. Our library is the first constant-time SIDH implementation and is up\u00a0to 2.9 times faster than the previous best (non-constant-time) SIDH software. The high speeds in this paper are driven by compact, inversion-free point and isogeny arithmetic and fast SIDH-tailored field arithmetic: on an Intel Haswell processor, generating ephemeral public keys takes 46 million cycles for Alice and 52 million cycles for Bob, while computing the shared secret takes 44 million and 50 million cycles, respectively. The size of public keys is only 564 bytes, which is significantly smaller than most of the popular post-quantum key exchange alternatives. Ultimately, the size and speed of our software illustrates the strong potential of SIDH as a post-quantum key exchange candidate and we hope that these results encourage a wider cryptanalytic effort.<\/p>\n","protected":false},"excerpt":{"rendered":"
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-bit classical security levels. Our library is the first constant-time SIDH implementation and is up\u00a0to 2.9 times faster than the […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[243138,13558],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-238356","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-quantum","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"Springer","msr_edition":"Advances in Cryptology \u2013 CRYPTO, 36th Annual International Conference on Cryptology, Santa Barbara","msr_affiliation":"","msr_published_date":"2016-08-14","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"572-601","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"http:\/\/rd.springer.com\/chapter\/10.1007\/978-3-662-53018-4_21","msr_doi":"10.1007\/978-3-662-53018-4_21","msr_publication_uploader":[{"type":"url","title":"http:\/\/rd.springer.com\/chapter\/10.1007\/978-3-662-53018-4_21","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1007\/978-3-662-53018-4_21","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/rd.springer.com\/chapter\/10.1007\/978-3-662-53018-4_21"}],"msr-author-ordering":[{"type":"user_nicename","value":"craigco","user_id":31476,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=craigco"},{"type":"user_nicename","value":"plonga","user_id":33271,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=plonga"},{"type":"user_nicename","value":"mnaehrig","user_id":32976,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=mnaehrig"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[144840,901101],"msr_project":[428250,482301,239768],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":428250,"post_title":"Post-quantum Cryptography","post_name":"post-quantum-cryptography","post_type":"msr-project","post_date":"2018-04-30 12:33:53","post_modified":"2024-09-30 21:14:11","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/post-quantum-cryptography\/","post_excerpt":"Cryptography in the era of quantum computers The private communication of individuals and organizations is protected online by cryptography. Cryptography protects our information as it travels over and is stored on the internet\u2014whether making a purchase from an online store, uploading data to the cloud, or accessing work email remotely. Our research and engineering work has focused on protecting private information and communication from the possible threat of future quantum computers. Quantum Computers will advance…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/428250"}]}},{"ID":482301,"post_title":"Supersingular Isogeny Key Encapsulation (SIKE)","post_name":"sike","post_type":"msr-project","post_date":"2018-04-30 12:34:55","post_modified":"2022-12-09 11:18:07","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/sike\/","post_excerpt":"SIKE and SIDH are insecure and should not be used. For more information, please refer to\u00a0the SIKE team's statement to NIST. Supersingular Isogeny Key Encapsulation (SIKE)\u00a0is a\u00a0post-quantum cryptography collaboration\u00a0between researchers and engineers at Amazon, Florida Atlantic University, Infosec Global, Microsoft Research, Radboud University, Texas Instruments, Universit\u00e9 de Versailles, and the University of Waterloo. SIKE is a family of post-quantum key encapsulation mechanisms based on the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange protocol. The algorithms use…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/482301"}]}},{"ID":239768,"post_title":"SIDH Library","post_name":"sidh-library","post_type":"msr-project","post_date":"2016-06-17 15:29:22","post_modified":"2022-12-09 11:20:50","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/sidh-library\/","post_excerpt":"SIKE and SIDH are insecure and should not be used. For more information, please refer to\u00a0the SIKE team's statement to NIST. SIDH\u00a0Library\u00a0is a fast and portable software library that implements a new suite of algorithms for supersingular isogeny Diffie-Hellman key exchange [1]. The chosen parameters aim to provide 128 bits of security against attackers running a large-scale quantum computer, and 192 bits of security against classical algorithms. SIDH has the option of a hybrid key…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/239768"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/238356"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/238356\/revisions"}],"predecessor-version":[{"id":522669,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/238356\/revisions\/522669"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=238356"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=238356"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=238356"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=238356"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=238356"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=238356"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=238356"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=238356"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=238356"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=238356"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=238356"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=238356"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=238356"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=238356"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=238356"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=238356"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}