Is the concept of provably secure hash the same as entropy smoothing hash functions?

In the tutorial Sequences of Games: A Tool for Taming Complexity in Security Proofs V. Shoup shows us a proof of semantic security of a hashed ElGamal encryption.

In order to get that proof (pag. 9) he put the following condition: we need a family of keyed "hash" functions $\mathcal{H} := \{H_k\}_{k\in K}$ where each $H_k$ is a function mapping $G$ to $\{0,1\}^l$ ($l$ a positive integer and $G$ is a group) such that this family $\mathcal{H}$ is "entropy smoothing".

He tells us that "entropy smoothing" gives us some kind of guarantee that makes it hard to distinguish $(k,H_k(\delta))$ from $(k,h)$, where $k$ is a random element of $K$, $\delta$ is a random element of $G$, and $h$ is a random element of $\{0,1\}^l$.

The author said there are ways to construct entropy smoothing hash functions, but it's just a conjecture that ad-hoc hash functions own this property.

  • 1
    $\begingroup$ I'm not 100% sure, but I think the 'entropy smoothing' property is strictly weaker than the standard security guarantees of a cryptographic hash. What I think he's saying is that a standard cryptographic hash is probably entropy-smoothing, but those hashes (e.g. SHA256) don't have formal proofs that they satisfy this property. $\endgroup$
    – pg1989
    Feb 14 '16 at 2:23
  • 2
    $\begingroup$ Just to be clear: No, entropy-smoothing hashes and standard cryptographic hashes are not the same. Shoup is saying that it's probably fine to treat them like they are the same, though. $\endgroup$
    – pg1989
    Feb 14 '16 at 2:26
  • 3
    $\begingroup$ "entropy smoothing" appears to be the same as "a strong extractor". ​ ​ $\endgroup$
    – user991
    Feb 14 '16 at 3:34

Ricky already gave the answer, but here are some additional details.

"Entropy smoothing" hash functions are randomness extractors. Extractors are functions that extract almost uniform bits from weak sources of entropy. In a way, they spread the min-entropy of the input source almost evenly over the (shorter) extracted source, hence the smoothing.

The Leftover Hash Lemma asserts that a strong randomness extractor can be constructed using a family of pairwise independent hash functions. So, if $\mathcal{H}$ in your statement were such a family, you get $(k, H_k(\delta)) \approx (k, h)$.

  • $\begingroup$ Thanks a lot people. You really gave me a light. Thanks htdawoud, pg1989 and Ricky Demer. $\endgroup$ Mar 22 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.