Cryptography
zero-knowledge-proofs commitments
Updated Sun, 10 Jul 2022 21:06:31 GMT

Zero-knowledge proof of committed value


I am considering the following questions and would appreciate any help.

Problem formulation:

Suppose Alice holds a secret value $x$ and there is a public Boolean predicate function $\texttt{Pred}$ that applies to $x$, $\texttt{Pred}: x \rightarrow \{0,1\}$. A sample predicate function can be whether the input $x$ is in a certain range or not.

Now Alice computes $y\gets\texttt{Pred}(x)$, but instead of publishing $y$, it publishes the encryption of $y$, $\texttt{Enc(y)}$ or commit to this value $\texttt{comm}_y$. Is it possible for Alice to prove that the encrypted value or the committed value is correctly computed by evaluating $\texttt{Pred}$ over $x$ without revealing $x$ and $y$?

(Please make additional assumptions if needed to solve this problem).




Solution

Yes it's possible, but you need to find equations $E_1, E_2$ which allow you to check: $$\texttt{Enc}(y)=c \iff E_1(y, c) $$ $$\texttt{Pred}(x) = y \iff E_2 (x,y) $$

Then you have to find a zero-knowledge proof-system which authorize you to prove equations such as $E_1, E_2$. For example, if these equations are in a bilinear group context, then Groth-Sahai perfectly fits : https://eprint.iacr.org/2007/155

Or if $E_1$ and $E_2$ are circuits, you can look this : https://eprint.iacr.org/2017/872.pdf

ps : In your case, because, there is no public information at all about x; It seems easy to cheat with a false $x$, but I'm assuming you have already thought about this.





Comments (2)

  • +0 – Hi, this is really helpful. Can I interpret this as it will also work for commitment schemes. For example, assume $y=f(x)$, and there will be commitments $com_x$ and $com_y$, then I can prove (without revealing x and y) that the committed value of $com_y$, is computed by applying $f()$ over the committed value of $com_x$? — Jun 14, 2021 at 16:09  
  • +0 – Commitments are a part of the proof, thus the answer to your question is "yes for someone who knows the randomness of the commitments". — Jun 14, 2021 at 16:55  


External Links

External links referenced by this document: