1
$\begingroup$

For a good (unkeyed) hash function, if a part of the input is random, is it fair to assume that the output will also be randomised? More specifically, suppose $H$ has an $n$-bit output, and we write its input as $x||y$ where $y$ has $n$-bits and $x$ is of arbitrary length. If $y$ is sampled uniformly at random from $\{0,1\}^n$, can we argue that (for some fixed $x$) $H(x||y)$ will also be uniformly distributed over $\{0,1\}^n$ (up to some small error term)? It seems this should informally follow from things like avalanche effect, but I'm not sure how we can argue this, without any idealised assumptions on the hash function.

$\endgroup$
3

1 Answer 1

2
$\begingroup$

In general the process of converting from "partial randomness" to "uniform randomness" is known as randomness extraction. One can show that "hashes" are good randomness extractors, but these hashes are universal hash functions, not cryptographic hash functions. See the statement of the Leftover Hash Lemma.

This is all to say that the natural way to convert your intuitive hope for something into a provable result is

  1. replace your cryptographic hash function family with a 2-universal hash function family $\mathcal{F}$, where $\mathcal{F}\ni f: \mathcal{X}\to\{0,1\}^m$,
  2. Replace sampling $y\gets \{0,1\}^n$ with uniformly sampling a hash $f\gets \mathcal{F}$

If you do both of these, then the LHL says that if $m \leq H_\infty(X) - 2 \log(1/\epsilon)$, then

$$ \Delta((f, f(X)), (f,U)) \leq \epsilon, $$

where $U\gets \{0,1\}^m$ is uniform, e.g. you can replace your "unpredictable, but not random" $X$ with uniform $U$, even when an adversary gets to see which function $f$ you are hashing it with. Here, $H_\infty(X) = -\log\max_x\Pr[X = x]$ is a worst-case notion of Shannon entropy.

For concrete numbers, say $\epsilon = 2^{-32}$, and $H_\infty(X)\geq 128$, e.g. the most-common value that $X$ takes on occurs with probability below $2^{-128}$. Then one can extract $H_\infty(X) - 2\log(1/\epsilon) = 128 - 2\times 32 = 64$ random bits from $X$, and an adversary can only distinguish these extracted bits from uniform bits with probability at most $2^{-32}$. These numbers may not be appropriate for your application, but hopefully how LHL can be used in your application is clear.

That all being said, this is mostly of interest for provable results outside of an idealized model (which you indicated you are interested in). In practice, replacing the universal hash function family with a cryptographic hash appears to be common, see for example this.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for the response. For a good cryptographic hash function $H$, would you say it's fair to assume that $\{f_k(x) := H(x||k) \mid k \in \{0,1\}^n\}$ is a family of 2-way universal hash functions? Then we can directly use the Leftover Hash Lemma. $\endgroup$ Feb 6 at 18:15
  • $\begingroup$ @ArghyaBhattacharjee it is implied by the assumption that $H$ is a random oracle, so it is implied by a standard assumption. It's not clear to me how meaningfully better of an assumption it is to assume $H$ is 2-universal versus just a random oracle directly though --- I think that really depends on your tastes/applications. $\endgroup$
    – Mark Schultz-Wu
    Feb 6 at 19:40
  • $\begingroup$ @ArghyaBhattacharjee also I would suggest using $f'_k(x) :=H(k||x)$ instead. Prepending (rather than post-pending) strings is the typical way that domain separation is achieved, which seems to be what you want. $\endgroup$
    – Mark Schultz-Wu
    Feb 6 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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