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.




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.