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$$?

## 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.

• +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