{"id":186449,"date":"2011-06-23T00:00:00","date_gmt":"2011-06-29T18:46:44","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/leftover-hash-lemma-revisited\/"},"modified":"2016-08-22T11:31:21","modified_gmt":"2016-08-22T18:31:21","slug":"leftover-hash-lemma-revisited","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/leftover-hash-lemma-revisited\/","title":{"rendered":"Leftover Hash Lemma, Revisited"},"content":{"rendered":"
\n

The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks:<\/p>\n

    \n
  1. Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v= m – 2*log(1\/e), meaning that the entropy loss L = m-v= 2*log(1\/e).<\/li>\n
  2. Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source.<\/li>\n<\/ol>\n

    Quite surprisingly, we show that both limitations of the LHL \u2014 large entropy loss and large seed \u2014 can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1\/e) for the setting of deriving secret keys for most cryptographic applications, including signatures\/MACs, CPA\/CCA-secure encryption, etc. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2-L<\/sup>). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!) Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short “input seed” S into a longer “output seed” S’, and then use the resulting S’ as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true.<\/p>\n

    Despite that, we show that it is sound either: (1) when extracting a “small” (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*. Implication (2) suggests that the sample-then-extract approach is likely secure when used with “practical” PRGs, despite lacking a reductionist proof of security!<\/p>\n

    The paper will appear at CRYPTO 2011 and can be found at http:\/\/eprint.iacr.org\/2011\/088<\/p>\n<\/div>\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"

    The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks: Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v= m – 2*log(1\/e), meaning that […]<\/p>\n","protected":false},"featured_media":196215,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-186449","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/lAUU7aKK2Xk","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186449","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186449\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/196215"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=186449"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=186449"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=186449"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=186449"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=186449"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=186449"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=186449"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=186449"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=186449"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=186449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}