2
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\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$
    – Ruben De Smet
    Sep 18, 2021 at 11:47

0

Reset to default

Your Answer

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