1
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – Chenghong
    Commented Jun 14, 2021 at 16:09
  • $\begingroup$ Commitments are a part of the proof, thus the answer to your question is "yes for someone who knows the randomness of the commitments". $\endgroup$
    – Ievgeni
    Commented Jun 14, 2021 at 16:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.