I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality here; I don't care if an adversary can determine the pre-image from the output.
In a zk proof I can compute $m$ multivariate quadratic equations (in $\mathbb{F}_p$ where $p \approx 2^{254}$) with $n$ variables in $O(n+m)$. If we define the degree $d$ the complexity is $O(m+n*(d-1))$. This means I can define large systems of equations and compute them relatively cheaply. In a rank 1 constraint system the complexity is defined as a number of constraints. The most efficient hash algorithm, Poseidon, is ~200 constraints. So a system of 100 quadratic equations with 2 variables would be ~50% faster (at the cost of having 100x larger output, though this can be handled). It's also possible to choose a value $m$ at runtime based on the $n$ value.
Is there an approach here to build a collision resistant checksum algorithm using systems of polynomial equations? I'm imagining each polynomial using independent random values as coefficients. Remember, I don't care about reversibility, just collision resistance.
Looking at some papers I'm seeing time for solving quadratic systems with $m=n$ in the range of $O(2^{3m})$. Is this accurate? I'm looking at lots of different research and it's hard to get a clear picture of the safety relative to $m$ and $n$ values.
Thanks
