Join Log in
Score:1
Chenghong avatar Crypto

Zero-knowledge proof of committed value

jp flag
Chenghong

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

66
1 + 0
Score:0
Ievgeni avatar Crypto
cn flag
Ievgeni

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 + 2
Chenghong avatar
jp flag
Chenghong
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$?
0
Reply
Ievgeni avatar
cn flag
Ievgeni
Commitments are a part of the proof, thus the answer to your question is "yes for someone who knows the randomness of the commitments".
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.