# How a collision for a function can be for another one

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 ?

• Please tell us what ideas you have considered so far. – mentallurg Nov 23 '20 at 3:56
• Comments are not for extended discussion; this conversation has been moved to chat. – fgrieu Nov 23 '20 at 19:16
• @fgrieu: looks like math mode doesn't work in chat :-/ – cisnjxqu Nov 23 '20 at 20:39
• @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. – fgrieu Nov 23 '20 at 21:00