Let $f$ be some crypto hash function, say MD5 with output $n$ bits. Restrict the input to $n$ bits. Cryptographer told me it is open problem if such restricted collision exists, i.e. $f(x)=f(y),x \ne y$. It is widely believed they exists, since permutations are small fraction of all functions.
Is it possible to show for some popular hash function such collision exists, possibly conditionally?
In practice $f$ is implemented as computer program or can be represented as a boolean function or circuit.
In theory it is polynomial map $\mathbb{F}_2^n \mapsto \mathbb{F}_2^n$.
We don't have the explicit polynomials since they are expected to be of prohibitively large degree (unless the function is heavily backdoored), though we can compute them.
I thought about using the Jacobian conjecture in finite fields when having in mind $x^2 = x$ and hope that if we get zero determinant numerically the map is not invertible. IIRC some boolean derivatives can be computed in this restricted scenario, not sure if they are can help.
Can the Jacobian conjecture in finite fields be used?
