# Checksum algorithm using system of multivariate polynomials

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