Collision Resistance of Single-Layer Neural Nets
2026-06-02 • Cryptography and Security
Cryptography and SecurityComputational Complexity
AI summaryⓘ
The authors study how hard it is to find collisions, meaning different inputs that produce the same output, in single-layer binary neural networks. They focus on a threshold parameter and find that when this threshold is small, there's a simple method to quickly find many collisions. But when the threshold is large, the problem becomes much harder, and they prove an exponential difficulty for certain online algorithms using a concept called the overlap gap property (OGP). This work is the first to use OGP as a way to show that finding collisions is resistant to certain algorithmic attacks. However, extending these results to other types of algorithms remains open.
binary neural networkscollision findingactivation functionthreshold scaleoverlap gap propertyonline algorithmsrandom matrixexponential lower boundalgorithmic complexitycollision resistance
Authors
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina
Abstract
We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\mathbf{A} \in \mathbb{R}^{m\times n}$, an input $\mathbf{x} \in \{-1,1\}^n$ is mapped to a binary output vector $\varphi(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$, where $\varphi$ is an activation function with constant behavior on $[κ, \infty)$ for some threshold $κ\geq 0$. We identify the threshold scale $κ=Θ(1/\sqrtα)$, where $α=m/n$, as separating two complementary phenomena. When $κ\ll 1/\sqrtα$, we give a simple online algorithm that efficiently produces extensive collisions. When $κ\gg 1/\sqrtα$, for a natural \emph{randomized} non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new ``worst-case'' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.