{"id":168212,"date":"2010-07-01T00:00:00","date_gmt":"2010-07-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/improved-fault-tolerance-and-secure-computation-on-sparse-networks\/"},"modified":"2018-10-16T20:10:26","modified_gmt":"2018-10-17T03:10:26","slug":"improved-fault-tolerance-and-secure-computation-on-sparse-networks","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/improved-fault-tolerance-and-secure-computation-on-sparse-networks\/","title":{"rendered":"Improved Fault Tolerance and Secure Computation on Sparse Networks"},"content":{"rendered":"

In the problem of almost-everywhere agreement<\/em> (denoted a.e. agreement), introduced by Dwork, Peleg, Pippenger, and Upfal [STOC \u201986], n<\/em> parties want to reach agreement on an initially held value, despite the possible disruptive and malicious behavior of up to t<\/em> of them. So far this is reminiscent of the classical Byzantine agreement<\/em> problem, except that in the alternative formulation the underlying connectivity graph is sparse<\/em>\u2014i.e., not all parties share point-to-point reliable channels\u2014thus modeling the actual connectivity of real communication networks. In this setting, one may not be able to guarantee agreement amongst all honest parties, and some of them, say x<\/em>, must be given up. Thus, in this line of work the goal is to be able to tolerate a high value for t<\/em> (a constant fraction of n<\/em> is the best possible) while minimizing x<\/em>. As shown in the original paper, the dependency on d<\/em>, the degree of the network, to achieve this goal is paramount.<\/p>\n

Indeed, the best polynomial-time a.e. agreement protocol tolerating a constant fraction of corruptions t<\/em>\u2009=\u2009\u03b1n<\/em>, for some constant \u03b1<\/em>>\u20090 (presented in the original paper, over two decades ago) has parameters, d<\/em>\u2009=\u2009n<\/em> \u03b5<\/em> <\/sup> for constant \u03b5<\/em>>\u20090 and x<\/em>\u2009=\u2009\u03bct<\/em> for some constant \u03bc<\/em>>\u20091. In this work, we significantly improve on the above parameters obtaining a protocol with t<\/em>\u2009=\u2009\u03b1n<\/em>, d<\/mi>=<\/mo>O<\/mi><\/mrow>(<\/mo>log<\/mi>q<\/mi><\/msup>⁡<\/mo>n<\/mi>)<\/mo><\/math>\">d<\/span>=<\/span>O<\/span><\/span><\/span>(<\/span>log<\/span>q<\/span><\/span><\/span>n<\/span>)<\/span><\/span><\/span><\/span><\/span>, for constant q<\/em>\u2009>\u20090 and x<\/mi>=<\/mo>O<\/mi><\/mrow>(<\/mo>t<\/mi>log<\/mi>⁡<\/mo>n<\/mi><\/mrow><\/mfrac>)<\/mo><\/math>\">x<\/span>=<\/span>O<\/span><\/span><\/span>(<\/span>t<\/span>log<\/span><\/span>n<\/span><\/span><\/span>)<\/span><\/span><\/span><\/span><\/span>. Our approach follows that of Dwork et al.<\/em> of reducing the a.e. agreement problem to constructing a reliable transmission scheme between pairs of nodes for a large fraction of them; however, given our setting\u2019s more stringent conditions\u2014poly-logarithmic degree and a linear number of corruptions, such a task is significantly harder.<\/p>\n

We also consider the problem of secure computation<\/em> on partially connected networks, as formulated by Garay and Ostrovsky [Eurocrypt \u201908], and as a corollary to our main result obtain an almost-everywhere secure multi-party computation protocol with the same parameters as above, again significantly improving on the bound on the number of left-out parties\u2014x<\/mi>=<\/mo>O<\/mi><\/mrow>(<\/mo>t<\/mi>log<\/mi>⁡<\/mo>n<\/mi><\/mrow><\/mfrac>)<\/mo><\/math>\">x<\/span>=<\/span>O<\/span><\/span><\/span> (<\/span>t<\/span>log<\/span><\/span>n<\/span><\/span><\/span>)\u00a0<\/span><\/span><\/span><\/span><\/span> for t<\/em>\u2009\u2264\u2009\u03b1n<\/em> corruptions, as opposed to x<\/mi>=<\/mo>O<\/mi><\/mrow>(<\/mo>t<\/mi>)<\/mo><\/math>\">x<\/span>=<\/span>O<\/span><\/span><\/span>(<\/span>t<\/span>)<\/span><\/span><\/span><\/span><\/span><\/span> in the original work.<\/p>\n","protected":false},"excerpt":{"rendered":"

In the problem of almost-everywhere agreement (denoted a.e. agreement), introduced by Dwork, Peleg, Pippenger, and Upfal [STOC \u201986], n parties want to reach agreement on an initially held value, despite the possible disruptive and malicious behavior of up to t of them. So far this is reminiscent of the classical Byzantine agreement problem, except that […]<\/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":[13561,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-168212","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","msr_edition":"Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II","msr_affiliation":"","msr_published_date":"2010-07-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"249\u2013260","msr_chapter":"","msr_isbn":"978-3-642-14161-4","msr_journal":"","msr_volume":"6199","msr_number":"","msr_editors":"","msr_series":"Lecture Notes in Computer Science","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":"http:\/\/dx.doi.org\/10.1007\/978-3-642-14162-1_21","msr_doi":"10.1007\/978-3-642-14162-1_21","msr_publication_uploader":[{"type":"url","title":"http:\/\/dx.doi.org\/10.1007\/978-3-642-14162-1_21","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1007\/978-3-642-14162-1_21","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/dx.doi.org\/10.1007\/978-3-642-14162-1_21"}],"msr-author-ordering":[{"type":"user_nicename","value":"nichandr","user_id":33084,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=nichandr"},{"type":"text","value":"Juan A. Garay","user_id":0,"rest_url":false},{"type":"text","value":"Rafail Ostrovsky","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[144675,144887,144938],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168212"}],"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\/168212\/revisions"}],"predecessor-version":[{"id":409919,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168212\/revisions\/409919"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=168212"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=168212"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=168212"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=168212"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=168212"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=168212"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=168212"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=168212"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=168212"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=168212"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=168212"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=168212"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=168212"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=168212"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=168212"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=168212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}