We have two bit strings $x\in\{0,1\}^q$ , $y\in\{0,1\}^w$ of length $q$ bits, and $w$ bits. The notation $x\mathbin\|y$ means $(q+w)$ bits long concatenation,

And the functions: $H∶\ \{0,1\}^* \to \{0,1\}^n$
and $F∶\ \{0,1\}^* \to \{0,1\}^{n+6}$ defined in terms of $H$ as $$F(x) = 000\mathbin\|H(1\mathbin\|x)\mathbin\|111$$

How can a collision $(x_1, x_2)$ for $F$ be turned into a collision for $H$ ?

Can any one please explain why, is it because $F$ has also $H(1\|x)$ in it and $F$ implies $H$ ? Or are any collision for $F$ will be a collision for $H$ also ?

  • 3
    $\begingroup$ Please tell us what ideas you have considered so far. $\endgroup$ – mentallurg Nov 23 '20 at 3:56
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – fgrieu Nov 23 '20 at 19:16
  • $\begingroup$ @fgrieu: looks like math mode doesn't work in chat :-/ $\endgroup$ – cisnjxqu Nov 23 '20 at 20:39
  • $\begingroup$ @cisnjxqu : Yes, known limitation. That's something for crypto-meta, or the general meta, or the side channel, but not for comment. These two might eventually vanish. $\endgroup$ – fgrieu Nov 23 '20 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.