# Is the subset of hash digest collision-resistant if hash function is collision-resistant?

Let $H(\cdot)$ be a collision resistant hash function, $H:\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^n$,

We define a new $H':\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^k$, where we randomly pick $k$ bit positions of $H(\cdot)$.

If we let the adversary, $\mathcal{A}$ , know those $k$ positions, does finding a collision for $H'(\cdot)$ still require $\mathcal{A}$ to ask $2^{k/2}$ queries to $H(\cdot)$ ? Can she do better? Also, if we hide those $k$ positions from $\mathcal A$, is it harder for her?

OK, assuming a setup whereby even if the location of the $k$ bits are unknown the guess or is told by an honest party whether his guess is correct, one can say the following.

Define a collision resistant hash with $n$ bit output as one which requires $O(2^{n/2})$ guesses before finding a collision.

If there was a way of finding a collision in an arbitrary $k$ bit subset in time strictly less than $O(2^{k/2})$ the the overall time would be reduced by attacking, say the $k$ bits and the remaining $n-k$ bits separately (in time strictly less than $O(2^{(n-k)/2})$) getting an overall attack time strictly less than $O(2^{n/2}).$

If $k$ needed to be bounded by some function of $n$ you could get the same result by partitioning into $\lceil n/k\rceil$ subblocks of length $k$ each.

If the multiplicative speedup factor for a k bit block was $2^{-\theta k}$ with $\theta \in (0,1),$ your overall speedup would be $$2^{-\lfloor n/k \rfloor \theta k}$$

approaching

$$2^{- \theta n}.$$ If the weakness was local for a specific $k$ bits, the saving would only be

$$2^{- \theta k}$$ but still contradict the definition of collision resistant $n$ bit hash function.