1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1

Your Answer

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

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