{"id":368537,"date":"2017-03-02T13:02:10","date_gmt":"2017-03-02T21:02:10","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&p=368537"},"modified":"2018-10-16T21:38:45","modified_gmt":"2018-10-17T04:38:45","slug":"improved-ot-extension-transferring-short-secrets","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/improved-ot-extension-transferring-short-secrets\/","title":{"rendered":"Improved OT Extension for Transferring Short Secrets"},"content":{"rendered":"

We propose an optimization and generalization of OT extension of Ishai et al. of Crypto 2003. For computational security parameter k<\/em>, our OT extension for short secrets offers O<\/em>(logk<\/em>) factor performance improvement in communication and computation, compared to prior work. In concrete terms, for today\u2019s security parameters, this means approx. factor 2-3 improvement.<\/p>\n

This results in corresponding improvements in applications relying on such OT. In particular, for two-party semi-honest SFE, this results in O<\/em>(logk<\/em>) factor improvement in communication over state of the art Yao Garbled Circuit, and has the same asymptotic complexity as the recent multi-round construction of Kolesnikov and Kumaresan of SCN 2012. For multi-party semi-honest SFE, where their construction is inapplicable, our construction implies O<\/em>(logk<\/em>) factor communication and computation improvement over best previous constructions. As with our OT extension, for today\u2019s security parameters, this means approximately factor 2 improvement in semi-honest multi-party SFE.<\/p>\n

Our building block of independent interest is a novel IKNP-based framework for 1-out-of-n<\/em> OT extension, which offers O<\/em>(logn<\/em>) factor performance improvement over previous work (for n<\/em> \u2264 k<\/em>), and concrete factor improvement of up to 5 for today\u2019s security parameters (n<\/em>=k<\/em>=128).<\/p>\n

Our protocol is the first practical OT with communication\/ computation cost sublinear in the security parameter (prior sublinear constructions Ishai et al. [15,16] are not efficient in concrete terms).<\/p>\n","protected":false},"excerpt":{"rendered":"

We propose an optimization and generalization of OT extension of Ishai et al. of Crypto 2003. For computational security parameter k, our OT extension for short secrets offers O(logk) factor performance improvement in communication and computation, compared to prior work. In concrete terms, for today\u2019s security parameters, this means approx. factor 2-3 improvement. This results […]<\/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":"","msr-author-ordering":null,"msr_publishername":"Springer Berlin Heidelberg","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"54-70","msr_page_range_start":"54","msr_page_range_end":"70","msr_series":"","msr_volume":"8043","msr_copyright":"","msr_conference_name":"Advances in Cryptology - CRYPTO 2013","msr_doi":"10.1007\/978-3-642-40084-1_4","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2013-08-18","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-40084-1_4","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13558],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-368537","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"Springer Berlin Heidelberg","msr_edition":"","msr_affiliation":"","msr_published_date":"2013-08-18","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"54-70","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"8043","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":"368861","msr_publicationurl":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-40084-1_4","msr_doi":"10.1007\/978-3-642-40084-1_4","msr_publication_uploader":[{"type":"file","title":"otext_crypto13","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/03\/otext_crypto13.pdf","id":368861,"label_id":0},{"type":"url","title":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-40084-1_4","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1007\/978-3-642-40084-1_4","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-40084-1_4"}],"msr-author-ordering":[{"type":"text","value":"Vladimir Kolesnikov","user_id":0,"rest_url":false},{"type":"user_nicename","value":"rakumare","user_id":36197,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=rakumare"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/368537","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":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/368537\/revisions"}],"predecessor-version":[{"id":537688,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/368537\/revisions\/537688"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=368537"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=368537"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=368537"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=368537"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=368537"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=368537"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=368537"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=368537"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=368537"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=368537"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=368537"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=368537"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=368537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}