{"id":159781,"date":"2010-01-01T00:00:00","date_gmt":"2010-01-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/faster-computation-of-the-tate-pairing\/"},"modified":"2018-10-16T21:35:20","modified_gmt":"2018-10-17T04:35:20","slug":"faster-computation-of-the-tate-pairing","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/faster-computation-of-the-tate-pairing\/","title":{"rendered":"Faster Computation of the Tate Pairing"},"content":{"rendered":"<div class=\"asset-content\">\n<p>This paper proposes new explicit formulas for the doubling and addition steps in Miller&#8217;s algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller&#8217;s algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curves in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This paper proposes new explicit formulas for the doubling and addition steps in Miller&#8217;s algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards [&hellip;]<\/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":[193715],"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-159781","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"Elsevier","msr_edition":"Journal of Number Theory","msr_affiliation":"","msr_published_date":"2010-01-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"Journal of Number Theory","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"doi:10.1016\/j.jnt.2010.05.013","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":"207356","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"arene-lange-naehrig-ritzenthaler-2010-eprint.pdf","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/arene-lange-naehrig-ritzenthaler-2010-eprint.pdf","id":207356,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":207356,"url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/arene-lange-naehrig-ritzenthaler-2010-eprint.pdf"}],"msr-author-ordering":[{"type":"text","value":"Christophe Arene","user_id":0,"rest_url":false},{"type":"text","value":"Tanja Lange","user_id":0,"rest_url":false},{"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"},{"type":"text","value":"Christophe Ritzenthaler","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[239792],"publication":[],"video":[],"download":[],"msr_publication_type":"article","related_content":{"projects":[{"ID":239792,"post_title":"Elliptic Curve Cryptography (ECC)","post_name":"elliptic-curve-cryptography-ecc","post_type":"msr-project","post_date":"2016-06-29 20:49:17","post_modified":"2020-03-31 12:25:10","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/elliptic-curve-cryptography-ecc\/","post_excerpt":"In the last 25 years, Elliptic Curve Cryptography (ECC) has become a mainstream primitive for cryptographic protocols and applications. ECC has been standardized for use in key exchange and digital signatures. This project focuses on efficient generation of parameters and implementation of ECC and pairing-based crypto primitives, across architectures and platforms.","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/239792"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/159781","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":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/159781\/revisions"}],"predecessor-version":[{"id":409502,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/159781\/revisions\/409502"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=159781"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=159781"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=159781"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=159781"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=159781"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=159781"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=159781"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=159781"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=159781"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=159781"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=159781"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=159781"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=159781"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=159781"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=159781"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=159781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}