0
$\begingroup$

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(x\right)$ is also collision resistant hash family?

Im thinking that $\mathcal{H}$ would not be collision resistant hash family but I cant find an exact counter example of $x \neq x'$ such that $W_{s}\left(x\right) = W_{s}\left(x'\right)$. My guess was to prove using induction that we can deduce $k$ bits and still consided to be a collision resistant hash function, even if $k=n-1$ which will lead us to a function with image of 1 bit and that obviously wont be valid hash function.

$\endgroup$
3
$\begingroup$

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(x\right)$ is also collision resistant hash family?

In general, no.

Let us assume that $\mathcal{H}'$ is a collision resistant hash family, and define $\mathcal{H}_k(x || b) = \mathcal{H}'_k(x) || b$, where $b$ is a single bit.

$\mathcal{H}$ is collision resistant (as a collision in $\mathcal{H}_k$ would imply a collision in $\mathcal{H}'_k$); however $\mathcal{W}$ is not, as $\mathcal{W}_k(00) = \mathcal{W}_k(01)$

$\endgroup$

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.