Supersingular isogeny Die-Hellman (SIDH) is an attractive candidate for postquantum key exchange, in large part due to its relatively small public key sizes. A recent paper by Azarderakhsh, Jao, Kalach, Koziel and Leonardi showed that the public keys dened in Jao and De Feo’s original SIDH scheme can be further compressed by around a factor of two, but reported that the performance penalty in utilizing this compression blew the overall SIDH runtime out by more than an order of magnitude. Given that the runtime of SIDH key exchange is currently its main drawback in relation to its lattice- and codebased post-quantum alternatives, an order of magnitude performance penalty for a factor of two improvement in bandwidth presents a trade-o that is unlikely to favor public-key compression in many scenarios.<\/p>\n
In this paper, we propose a range of new algorithms and techniques that accelerate SIDH public key-compression by more than an order of magnitude, making it roughly as fast as a round of standalone SIDH key exchange, while further reducing the size of the compressed public keys by approximately 13%. These improvements enable the practical use of compression, achieving public keys of only 330 bytes for the concrete parameters used to target 128 bits of quantum security and further strengthens SIDH as a promising post-quantum primitive.<\/p>\n","protected":false},"excerpt":{"rendered":"
Supersingular isogeny Die-Hellman (SIDH) is an attractive candidate for postquantum key exchange, in large part due to its relatively small public key sizes. A recent paper by Azarderakhsh, Jao, Kalach, Koziel and Leonardi showed that the public keys dened in Jao and De Feo’s original SIDH scheme can be further compressed by around a factor […]<\/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],"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-365990","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-quantum","msr-locale-en_us"],"msr_publishername":"Springer-Verlag","msr_edition":"","msr_affiliation":"","msr_published_date":"2016-10-4","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","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:\/\/eprint.iacr.org\/2016\/963","msr_doi":"","msr_publication_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"http:\/\/eprint.iacr.org\/2016\/963","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/eprint.iacr.org\/2016\/963"}],"msr-author-ordering":[{"type":"user_nicename","value":"Craig Costello","user_id":31476,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Craig Costello"},{"type":"text","value":"David Jao","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Patrick Longa","user_id":33271,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Patrick Longa"},{"type":"user_nicename","value":"Michael Naehrig","user_id":32976,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Michael Naehrig"},{"type":"text","value":"Joost Renes","user_id":0,"rest_url":false},{"type":"text","value":"David Urbanik","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"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\/365990","targetHints":{"allow":["GET"]}}],"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":3,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/365990\/revisions"}],"predecessor-version":[{"id":736681,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/365990\/revisions\/736681"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=365990"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=365990"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=365990"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=365990"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=365990"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=365990"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=365990"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=365990"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=365990"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=365990"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=365990"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=365990"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=365990"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=365990"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=365990"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=365990"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}