{"id":168201,"date":"2014-08-01T00:00:00","date_gmt":"2014-08-01T00:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/privacy-amplification-with-asymptotically-optimal-entropy-loss\/"},"modified":"2018-10-16T21:11:53","modified_gmt":"2018-10-17T04:11:53","slug":"privacy-amplification-with-asymptotically-optimal-entropy-loss","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/privacy-amplification-with-asymptotically-optimal-entropy-loss\/","title":{"rendered":"Privacy amplification with asymptotically optimal entropy loss"},"content":{"rendered":"<p>We study the problem of &#8220;privacy amplification&#8221;: key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve&#8217;s point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string <span id=\"MathJax-Element-1-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-1\" class=\"math\"><span id=\"MathJax-Span-2\" class=\"mrow\"><span id=\"MathJax-Span-3\" class=\"mi\">R<\/span><\/span>\u00a0<\/span><span class=\"MJX_Assistive_MathML\">R<\/span><\/span> that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.).<\/p>\n<p>Because we make no computational assumptions, the entropy in R can come only from w. Thus such a protocol must minimize the entropy loss during its execution, so that R is as long as possible. The best previous results have entropy loss of <span id=\"MathJax-Element-2-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-4\" class=\"math\"><span id=\"MathJax-Span-5\" class=\"mrow\"><span id=\"MathJax-Span-6\" class=\"mi\">\u0398<\/span><span id=\"MathJax-Span-7\" class=\"mo\">(<\/span><span id=\"MathJax-Span-8\" class=\"msubsup\"><span id=\"MathJax-Span-9\" class=\"mi\">\u03ba<\/span>\u00a0<span id=\"MathJax-Span-10\" class=\"mn\">2<\/span>\u00a0<\/span><span id=\"MathJax-Span-11\" class=\"mo\">)<\/span><\/span>\u00a0<\/span><span class=\"MJX_Assistive_MathML\">\u0398(\u03ba2)<\/span><\/span> , where <span id=\"MathJax-Element-3-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-12\" class=\"math\"><span id=\"MathJax-Span-13\" class=\"mrow\"><span id=\"MathJax-Span-14\" class=\"mi\">\u03ba<\/span><\/span>\u00a0<\/span><span class=\"MJX_Assistive_MathML\">\u03ba<\/span><\/span> is the security parameter, thus requiring the password to be very long even for small values of <span id=\"MathJax-Element-4-Frame\" class=\"MathJax\"><span id=\"MathJax-Span-15\" class=\"math\"><span id=\"MathJax-Span-16\" class=\"mrow\"><span id=\"MathJax-Span-17\" class=\"mi\">\u03ba<\/span><\/span>\u00a0<\/span><span class=\"MJX_Assistive_MathML\">\u03ba<\/span><\/span> . In this work, we present the first protocol for information-theoretic key agreement that has entropy loss LINEAR in the security parameter. The result is optimal up to constant factors. We achieve our improvement through a somewhat surprising application of error-correcting codes for the edit distance.<\/p>\n<p>The protocol can be extended to provide also &#8220;information reconciliation,&#8221; that is, to work even when the two parties have slightly different versions of w (for example, when biometrics are involved).<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We study the problem of &#8220;privacy amplification&#8221;: key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an [&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":[13561,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-168201","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":"ACM - Association for Computing Machinery","msr_edition":"Journal of ACM","msr_affiliation":"","msr_published_date":"2014-08-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"29","msr_chapter":"","msr_isbn":"","msr_journal":"Journal of ACM","msr_volume":"61","msr_number":"5","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":"http:\/\/doi.acm.org\/10.1145\/2630064","msr_doi":"10.1145\/2630064","msr_publication_uploader":[{"type":"url","title":"http:\/\/doi.acm.org\/10.1145\/2630064","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1145\/2630064","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/doi.acm.org\/10.1145\/2630064"}],"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":"Bhavana Kanukurthi","user_id":0,"rest_url":false},{"type":"text","value":"Rafail Ostrovsky","user_id":0,"rest_url":false},{"type":"text","value":"Leonid Reyzin","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199562],"msr_event":[],"msr_group":[144938,144675,144887],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"article","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168201"}],"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\/168201\/revisions"}],"predecessor-version":[{"id":409901,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/168201\/revisions\/409901"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=168201"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=168201"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=168201"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=168201"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=168201"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=168201"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=168201"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=168201"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=168201"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=168201"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=168201"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=168201"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=168201"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=168201"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=168201"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=168201"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}