Are Neural Networks Collision Resistant?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917077529395200 |
|---|---|
| author | Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo |
| author_facet | Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo |
| contents | When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity of finding a collision in a single-layer neural net, where a collision is defined as two distinct sets of weights that assign the same labels to all data. For binary perceptrons with oscillating activation functions, we establish the emergence of an overlap gap property in the space of collisions. This is a topological property believed to be a barrier to the performance of efficient algorithms. The hardness is supported by numerical experiments using approximate message passing algorithms, for which the algorithms stop working well below the value predicted by our analysis. Neural networks provide a new category of candidate collision resistant functions, which for some parameter setting depart from constructions based on lattices. Beyond relevance to cryptography, our work uncovers new forms of computational hardness emerging in large neural networks which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_20262 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Are Neural Networks Collision Resistant? Benedetti, Marco Bogdanov, Andrej Malatesta, Enrico M. Mézard, Marc Perrupato, Gianmarco Rosen, Alon Schwartzbach, Nikolaj I. Zecchina, Riccardo Disordered Systems and Neural Networks Cryptography and Security Probability When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity of finding a collision in a single-layer neural net, where a collision is defined as two distinct sets of weights that assign the same labels to all data. For binary perceptrons with oscillating activation functions, we establish the emergence of an overlap gap property in the space of collisions. This is a topological property believed to be a barrier to the performance of efficient algorithms. The hardness is supported by numerical experiments using approximate message passing algorithms, for which the algorithms stop working well below the value predicted by our analysis. Neural networks provide a new category of candidate collision resistant functions, which for some parameter setting depart from constructions based on lattices. Beyond relevance to cryptography, our work uncovers new forms of computational hardness emerging in large neural networks which may be of independent interest. |
| title | Are Neural Networks Collision Resistant? |
| topic | Disordered Systems and Neural Networks Cryptography and Security Probability |
| url | https://arxiv.org/abs/2509.20262 |