conference paper
Leftover hash lemma revisited
LNCS
published
Boaz
Barak
author
Yevgeniy
Dodis
author
Hugo
Krawczyk
author
Olivier
Pereira
author
Krzysztof Z
Pietrzak
author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654
François
Standaert
author
Yu
Yu
author
CRYPTO: International Cryptology Conference
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 limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. 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, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. 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 expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research.
Springer2011
10.1007/978-3-642-22792-9_1
68411 - 20
yes
Barak, Boaz, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Z Pietrzak, François Standaert, and Yu Yu. “Leftover Hash Lemma Revisited,” 6841:1–20. Springer, 2011. <a href="https://doi.org/ 10.1007/978-3-642-22792-9_1">https://doi.org/ 10.1007/978-3-642-22792-9_1</a>.
Barak B, Dodis Y, Krawczyk H, Pereira O, Pietrzak KZ, Standaert F, Yu Y. 2011. Leftover hash lemma revisited. CRYPTO: International Cryptology Conference, LNCS, vol. 6841, 1–20.
B. Barak, Y. Dodis, H. Krawczyk, O. Pereira, K.Z. Pietrzak, F. Standaert, Y. Yu, in:, Springer, 2011, pp. 1–20.
B. Barak <i>et al.</i>, “Leftover hash lemma revisited,” presented at the CRYPTO: International Cryptology Conference, 2011, vol. 6841, pp. 1–20.
Barak B, Dodis Y, Krawczyk H, et al. Leftover hash lemma revisited. In: Vol 6841. Springer; 2011:1-20. doi:<a href="https://doi.org/ 10.1007/978-3-642-22792-9_1"> 10.1007/978-3-642-22792-9_1</a>
Barak, Boaz, et al. <i>Leftover Hash Lemma Revisited</i>. Vol. 6841, Springer, 2011, pp. 1–20, doi:<a href="https://doi.org/ 10.1007/978-3-642-22792-9_1"> 10.1007/978-3-642-22792-9_1</a>.
Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K. Z., Standaert, F., & Yu, Y. (2011). Leftover hash lemma revisited (Vol. 6841, pp. 1–20). Presented at the CRYPTO: International Cryptology Conference, Springer. <a href="https://doi.org/ 10.1007/978-3-642-22792-9_1">https://doi.org/ 10.1007/978-3-642-22792-9_1</a>
32402018-12-11T12:02:12Z2021-01-12T07:42:03Z