Are Neural Networks Collision Resistant?

Collision-resistant hash functions are a fundamental cryptographic primitive that rely on the computational hardness of finding two inputs that produce the same output. Motivated by this problem, we study the complexity of finding collisions in a family of neural networks with oscillating activation functions. A neural network trained on a classification task is specified by a set of weights assigning a label to each data point, and a collision is defined as two distinct weight configurations that produce the same labeling. We show that, within this class of neural networks, the space of collisions exhibits an overlap gap property, whereby certain overlap values between distinct solutions are forbidden. This property is a geometric feature of the solution landscape in high-dimensional random constraint satisfaction problems that has recently emerged as a powerful indicator of algorithmic barriers. Our analysis predicts a regime in which efficient algorithms fail to find collisions. This prediction is supported by numerical experiments using approximate message passing algorithms, which cease to return collisions well below the threshold predicted by theory. Neural networks, therefore, provide a class of candidate collision-resistant functions that, for suitable parameter choices, depart from existing constructions based on lattices. Beyond their cryptographic relevance, our results reveal forms of computational hardness in large neural networks that may be of independent interest.