Paper 2026/1044

Finding Random Collisions for Random Degree-2 Functions

Abstract

We study distributional collision resistance for random degree-2 functions over prime fields. Let $p$ be a prime and let \[ h:\mathbb{F}_p^N\to \mathbb{F}_p^M, \ x \mapsto (h_1(x), \dots, h_M(x)) \qquad M<N, \] be a random polynomial map where each coordinate $h_i$ is independently, uniformly chosen at random from all polynomials of degree at most 2 over $\mathbb{F}_p$. The ideal collision distribution is obtained by choosing \(x\gets\mathbb{F}_p^N\) and \(y\gets h^{-1}(h(x))\) uniformly at random and output $(x, y)$. We give an efficient algorithm whose output distribution is statistically close to this ideal collision distribution whenever \(p^{N - M}\) is superpolynomial. In other words, we show that random degree-2 functions are not distributionally collision-resistant if $p^{N - M}$ is superpolynomial, resolving an open question posed by Bitansky, Haitner, Komargodski, and Yogev (Eurocrypt 2019) in this parameter regime.