{"id":163892,"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\/delaying-mismatched-field-multiplications-in-pairing-computations\/"},"modified":"2021-03-29T08:08:55","modified_gmt":"2021-03-29T15:08:55","slug":"delaying-mismatched-field-multiplications-in-pairing-computations","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/delaying-mismatched-field-multiplications-in-pairing-computations\/","title":{"rendered":"Delaying Mismatched Field Multiplications in Pairing Computations"},"content":{"rendered":"<p>Miller\u2019s algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field\u00a0<span id=\"IEq1\" class=\"InlineEquation\"><span id=\"MathJax-Element-1-Frame\" class=\"MathJax\" style=\"font-style: normal;font-weight: normal;line-height: normal;font-size: 17px;text-indent: 0px;text-align: left;text-transform: none;letter-spacing: normal;float: none;direction: ltr;max-width: none;max-height: none;min-width: 0px;min-height: 0px;border: 0px;padding: 0px;margin: 0px\" role=\"presentation\" data-mathml=\"<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mrow class=\"MJX-TeXAtom-ORD\"><mi mathvariant=\"double-struck\">F<\/mi><\/mrow><mrow class=\"MJX-TeXAtom-ORD\"><msup><mi>p<\/mi><mi>k<\/mi><\/msup><\/mrow><\/msub><\/math>\"><span id=\"MathJax-Span-1\" class=\"math\"><span id=\"MathJax-Span-2\" class=\"mrow\"><span id=\"MathJax-Span-3\" class=\"msubsup\"><span id=\"MathJax-Span-4\" class=\"texatom\"><span id=\"MathJax-Span-5\" class=\"mrow\"><span id=\"MathJax-Span-6\" class=\"mi\">F<\/span><\/span><\/span><span id=\"MathJax-Span-7\" class=\"texatom\"><span id=\"MathJax-Span-8\" class=\"mrow\"><span id=\"MathJax-Span-9\" class=\"msubsup\"><span id=\"MathJax-Span-10\" class=\"mi\">p<\/span><span id=\"MathJax-Span-11\" class=\"mi\">k<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span> are multiplied by elements contained in proper subfields <span id=\"IEq2\" class=\"InlineEquation\"><span id=\"MathJax-Element-2-Frame\" class=\"MathJax\" style=\"font-style: normal;font-weight: normal;line-height: normal;font-size: 17px;text-indent: 0px;text-align: left;text-transform: none;letter-spacing: normal;float: none;direction: ltr;max-width: none;max-height: none;min-width: 0px;min-height: 0px;border: 0px;padding: 0px;margin: 0px\" role=\"presentation\" data-mathml=\"<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mrow class=\"MJX-TeXAtom-ORD\"><mi mathvariant=\"double-struck\">F<\/mi><\/mrow><mrow class=\"MJX-TeXAtom-ORD\"><msup><mi>p<\/mi><mrow class=\"MJX-TeXAtom-ORD\"><mi>k<\/mi><mrow class=\"MJX-TeXAtom-ORD\"><mo>\/<\/mo><\/mrow><mi>d<\/mi><\/mrow><\/msup><\/mrow><\/msub><\/math>\"><span id=\"MathJax-Span-12\" class=\"math\"><span id=\"MathJax-Span-13\" class=\"mrow\"><span id=\"MathJax-Span-14\" class=\"msubsup\"><span id=\"MathJax-Span-15\" class=\"texatom\"><span id=\"MathJax-Span-16\" class=\"mrow\"><span id=\"MathJax-Span-17\" class=\"mi\">F<\/span><\/span><\/span><span id=\"MathJax-Span-18\" class=\"texatom\"><span id=\"MathJax-Span-19\" class=\"mrow\"><span id=\"MathJax-Span-20\" class=\"msubsup\"><span id=\"MathJax-Span-21\" class=\"mi\">p(<\/span><span id=\"MathJax-Span-22\" class=\"texatom\"><span id=\"MathJax-Span-23\" class=\"mrow\"><span id=\"MathJax-Span-24\" class=\"mi\">k<\/span><span id=\"MathJax-Span-25\" class=\"texatom\"><span id=\"MathJax-Span-26\" class=\"mrow\"><span id=\"MathJax-Span-27\" class=\"mo\">\/<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><span class=\"MJX_Assistive_MathML\" role=\"presentation\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mrow class=\"MJX-TeXAtom-ORD\"><msup><mi>d)<\/mi><\/msup><\/mrow><\/msub><\/math><\/span><\/span><\/span>, and by elements in the base field <span id=\"IEq3\" class=\"InlineEquation\"><span id=\"MathJax-Element-3-Frame\" class=\"MathJax\" style=\"font-style: normal;font-weight: normal;line-height: normal;font-size: 17px;text-indent: 0px;text-align: left;text-transform: none;letter-spacing: normal;float: none;direction: ltr;max-width: none;max-height: none;min-width: 0px;min-height: 0px;border: 0px;padding: 0px;margin: 0px\" role=\"presentation\" data-mathml=\"<math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mrow class=\"MJX-TeXAtom-ORD\"><mi mathvariant=\"double-struck\">F<\/mi><\/mrow><mrow class=\"MJX-TeXAtom-ORD\"><mi>p<\/mi><\/mrow><\/msub><\/math>\"><span class=\"MJX_Assistive_MathML\" role=\"presentation\"><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><msub><mrow class=\"MJX-TeXAtom-ORD\"><mi mathvariant=\"double-struck\">F<\/mi><\/mrow><mrow class=\"MJX-TeXAtom-ORD\"><mi>p<\/mi><\/mrow><\/msub><\/math><\/span><\/span><\/span>. We show that significant speedups in pairing computations can be achieved by delaying these \u201cmismatched\u201d multiplications for an optimal number of iterations. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Miller\u2019s algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field\u00a0Fpk are multiplied by elements contained in proper subfields Fp(k\/d), and by elements in the base field Fp. We show that significant speedups in pairing computations can be achieved by delaying these \u201cmismatched\u201d [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"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-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-163892","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2010-7-1","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":"doi","viewUrl":"false","id":"false","title":"https:\/\/doi.org\/10.1007\/978-3-642-13797-6_14","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"C. Costello","user_id":0,"rest_url":false},{"type":"text","value":"C. Boyd","user_id":0,"rest_url":false},{"type":"text","value":"J. M. Gonz\u00e1lez Nieto","user_id":0,"rest_url":false},{"type":"text","value":"K. Koon-Ho Wong","user_id":0,"rest_url":false},{"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":[],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163892"}],"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\/163892\/revisions"}],"predecessor-version":[{"id":736624,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/163892\/revisions\/736624"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=163892"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=163892"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=163892"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=163892"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=163892"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=163892"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=163892"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=163892"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=163892"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=163892"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=163892"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=163892"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=163892"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=163892"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=163892"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}