We study the complexity of realizing the \u201cworst\u201d functions in several standard models of information-theoretic cryptography. In particular, for the case of security against passive adversaries, we obtain the following main results.<\/p>\n
OT complexity of secure two-party computation.<\/strong> Every function f<\/em>:[N<\/em>]\u00d7[N<\/em>]\u2009\u2192\u2009{0,1} can be securely evaluated using Correlated randomness complexity of secure two-party computation.<\/strong> Every function f<\/em>:[N<\/em>]\u00d7[N<\/em>]\u2009\u2192\u2009{0,1} can be securely evaluated using Communication complexity of private simultaneous messages.<\/strong> Every function f<\/em>:[N<\/em>]\u00d7[N<\/em>]\u2009\u2192\u2009{0,1} can be securely evaluated in the non-interactive model of Feige, Kilian, and Naor (STOC 1994) with messages of length Share complexity of forbidden graph access structures.<\/strong> For every graph G<\/em> on N<\/em> nodes, there is a secret-sharing scheme for N<\/em> parties in which each pair of parties can reconstruct the secret if and only if the corresponding nodes in G<\/em> are connected, and where each party gets a share of size The worst-case complexity of the best previous solutions was \u03a9(N<\/em>) for the first three problems and \u03a9(N<\/em>\/logN<\/em>) for the last one. The above results are obtained by applying general transformations to variants of private information retrieval (PIR) protocols from the literature, where different flavors of PIR are required for different applications.<\/p>\n","protected":false},"excerpt":{"rendered":" We study the complexity of realizing the \u201cworst\u201d functions in several standard models of information-theoretic cryptography. In particular, for the case of security against passive adversaries, we obtain the following main results. OT complexity of secure two-party computation. Every function f:[N]\u00d7[N]\u2009\u2192\u2009{0,1} can be securely evaluated using O~(N2\/3)O~(N2\/3) invocations of an oblivious transfer oracle. A similar […]<\/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":"317-342","msr_page_range_start":"317","msr_page_range_end":"342","msr_series":"","msr_volume":"8349","msr_copyright":"","msr_conference_name":"Theory of Cryptography","msr_doi":"10.1007\/978-3-642-54242-8_14","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":"2014-02-24","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-54242-8_14","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-368534","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":"2014-02-24","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"317-342","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"8349","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":"368858","msr_publicationurl":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-54242-8_14","msr_doi":"10.1007\/978-3-642-54242-8_14","msr_publication_uploader":[{"type":"file","title":"BIKK","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/03\/BIKK.pdf","id":368858,"label_id":0},{"type":"url","title":"https:\/\/link.springer.com\/chapter\/10.1007%2F978-3-642-54242-8_14","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1007\/978-3-642-54242-8_14","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-54242-8_14"}],"msr-author-ordering":[{"type":"text","value":"Amos Beimel","user_id":0,"rest_url":false},{"type":"text","value":"Yuval Ishai","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"},{"type":"text","value":"Eyal Kushilevitz","user_id":0,"rest_url":false}],"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\/368534","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\/368534\/revisions"}],"predecessor-version":[{"id":537650,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/368534\/revisions\/537650"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=368534"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=368534"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=368534"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=368534"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=368534"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=368534"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=368534"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=368534"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=368534"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=368534"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=368534"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=368534"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=368534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}