Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively.
Then, if I want to prove to someone that this computation have been computed properly without actually disclosing $x$, then I have to create a zero-knowledge proof of knowledge $\pi$ (which could be obtained through general purpose ZKPoK such us SNARKS, STARKS, ...) of an $x$ such that $h = H(x, y)$.
Until this point, everything is okey.
What if I do want someone else to verify the hash evaluation without revealing the private input $x$, not going through generic purpose ZKPoK; and more importantly: keeping some hash function properties such as determinism, uniformity and universality?
My first idea to solve this question is to find a function $f$ such that:
- $f(x)$ can be made public (so that anyone can easily check the computation $H(f(x), y)$).
- $f(x)$ also satisfies determinism,uniformity and universality.
In fact, if such a function $f$ exist, then I could just replace $H$ with $f$. Let's say that what I am trying to find is some computation that shares some of the properties that hash functions have but being much more efficiently (i.e., without the need of generic purpose proofs) verificable.
A second idea is to substitute the hashing mechanism by something else (e.g., encryption concatenated with a signature ...) that could be efficiently verifiable while at the same time keeping the mentioned properties.
