{"id":629649,"date":"2020-01-06T14:28:17","date_gmt":"2020-01-06T22:28:17","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&p=629649"},"modified":"2021-03-29T08:40:52","modified_gmt":"2021-03-29T15:40:52","slug":"b-sidh-supersingular-isogeny-diffie-hellman-using-twisted-torsion","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/b-sidh-supersingular-isogeny-diffie-hellman-using-twisted-torsion\/","title":{"rendered":"B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion"},"content":{"rendered":"

This paper explores a new way of instantiating isogeny-based cryptography in which parties can work in both the\u00a0(<\/mo>p<\/mi>+<\/mo>1<\/mn>)<\/mo><\/math>\">(<\/span>p<\/span>+<\/span>1<\/span>) <\/span><\/span><\/span><\/span><\/span>-torsion of a set of supersingular curves and in the\u00a0(<\/mo>p<\/mi>−<\/mo>1<\/mn>)<\/mo><\/math>\">(<\/span>p<\/span>\u2212<\/span>1<\/span>)<\/span><\/span><\/span><\/span><\/span>-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over\u00a0F<\/mi><\/mrow>p<\/mi>2<\/mn><\/msup><\/mrow><\/msub><\/math>\">F<\/span><\/span><\/span>p<\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00a0in general, restricting operations to the\u00a0x<\/em>-lines of both sets of twists allows all arithmetic to be carried out over\u00a0F<\/mi><\/mrow>p<\/mi>2<\/mn><\/msup><\/mrow><\/msub><\/math>\">F<\/span><\/span><\/span>p<\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u00a0as usual. Furthermore, since supersingular twists always have the same\u00a0F<\/mi><\/mrow>p<\/mi>2<\/mn><\/msup><\/mrow><\/msub><\/math>\">F<\/span><\/span><\/span>p<\/span>2<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>-rational\u00a0j<\/em>-invariant, the SIDH protocol remains unchanged when Alice and Bob are free to work in both sets of twists.<\/p>\n

This framework lifts the restrictions on the shapes of the underlying prime fields originally imposed by Jao and De Feo, and allows a range of new options for instantiating isogeny-based public key cryptography. These include alternatives that exploit Mersenne and Montgomery-friendly primes, as well as the possibility of significantly reducing the size of the primes in the Jao-De Feo construction at no known loss of asymptotic security. For a given target security level, the resulting public keys are smaller than the public keys of all of the key encapsulation schemes currently under consideration in the NIST post-quantum standardisation effort.<\/p>\n

The best known attacks against the instantiations proposed in this paper are the classical path finding algorithm due to Delfs and Galbraith and its quantum adapation due to Biasse, Jao and Sankar; these run in respective time\u00a0O<\/mi>(<\/mo>p<\/mi>1<\/mn>\/<\/mo><\/mrow>2<\/mn><\/mrow><\/msup>)<\/mo><\/math>\">O<\/span>(<\/span>p^(<\/span>1<\/span>\/<\/span><\/span><\/span>2<\/span><\/span><\/span><\/span>))<\/span><\/span><\/span><\/span><\/span>and\u00a0O<\/mi>(<\/mo>p<\/mi>1<\/mn>\/<\/mo><\/mrow>4<\/mn><\/mrow><\/msup>)<\/mo><\/math>\">O<\/span>(<\/span>p^(<\/span>1<\/span>\/<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span>))<\/span><\/span><\/span><\/span><\/span>, and are essentially memory-free. The upshot is that removing the big-O<\/em>\u2019s and obtaining concrete security estimates is a matter of costing the circuits needed to implement the corresponding isogeny. In contrast to other post-quantum proposals, this makes the security analysis of B-SIDH rather straightforward.<\/p>\n

Searches for friendly parameters are used to find several primes that range from 237 to 256 bits, which all offer a conjectured security comparable to the 434-bit prime used to target NIST level 1 security in the SIKE proposal. One noteworthy example is a 247-bit prime for which Alice\u2019s secret isogeny is 7901-smooth and Bob\u2019s secret isogeny is 7621-smooth.<\/p>\n","protected":false},"excerpt":{"rendered":"

This paper explores a new way of instantiating isogeny-based cryptography in which parties can work in both the\u00a0(p+1) -torsion of a set of supersingular curves and in the\u00a0(p\u22121)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over\u00a0Fp2\u00a0in general, restricting operations […]<\/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":[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-629649","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"Springer-Verlag","msr_edition":"","msr_affiliation":"","msr_published_date":"2020-12-5","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":"","msr_doi":"","msr_publication_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/eprint.iacr.org\/2019\/1145","label_id":"243109","label":0},{"type":"doi","viewUrl":"false","id":"false","title":"https:\/\/doi.org\/10.1007\/978-3-030-64834-3_15","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[],"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"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[144840],"msr_project":[428250],"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"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/629649"}],"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":5,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/629649\/revisions"}],"predecessor-version":[{"id":736678,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/629649\/revisions\/736678"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=629649"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=629649"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=629649"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=629649"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=629649"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=629649"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=629649"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=629649"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=629649"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=629649"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=629649"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=629649"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=629649"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=629649"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=629649"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=629649"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}