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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ I'm too lazy to write a long answer for this; if not, then there is a huge design error. Avalance effect is the key. Hash functions and the Avalanche effect How many bits in the resultant hash will change, if the x bits are changed in its the original input? see more at search $\endgroup$– kelalakaCommented Feb 5 at 22:04
-
$\begingroup$ Note that if $x$ is known, then the size $|y| =n$ is really important to be secure. This is posfix construction for hash-based simple signatures. $\endgroup$– kelalakaCommented Feb 5 at 23:02
-
$\begingroup$ An interesting question would be: Is the output of a perfect hash function more random when feeding it with random input compared to feeding it with a simple binary counter? $\endgroup$– U. WindlCommented Feb 6 at 9:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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
- 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$,
- 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.
-
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$ Commented 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 ♦Commented 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 ♦Commented Feb 6 at 20:09