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:

  1. $f(x)$ can be made public (so that anyone can easily check the computation $H(f(x), y)$).
  2. $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.

  • $\begingroup$ What is the status of $y$? $\endgroup$
    – Ievgeni
    Sep 16, 2021 at 13:37
  • $\begingroup$ What do you mean by status? $\endgroup$
    – Bean Guy
    Sep 16, 2021 at 13:45
  • $\begingroup$ Is it publicly known? Or is it secret? $\endgroup$
    – Ievgeni
    Sep 16, 2021 at 13:48
  • $\begingroup$ $x$ is the public input and $y$ is the private input. $\endgroup$
    – Bean Guy
    Sep 16, 2021 at 14:10
  • 1
    $\begingroup$ I don't see how; a standard Pedersen commitment $C = xG + yH$ is perfectly hiding, and afaik undistinguishable from random. On the other hand; that would integrate your $y$ variable into the $f(x)$ function and require it to be uniform random, so it's not strictly what you're after. $\endgroup$ Sep 18, 2021 at 11:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy