# Is there a practical zero-knowledge proof for this special discrete log equation?

We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal. Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$. There are two parties, Alice and Bob:

• Alice knows: $g$, $h$, $x_1$, $x_2$ and $(a,b,c)$,
• Bob knows: $g$, $h$ and $(a,b,c)$.

Can Alice prove to Bob in zero knowledge that she knows $x_1$ and $x_2$ such that $(a,b,c) = (g^{x_1} , x_2·(h^{x_1}), h^{x_2})$?

This proof must be practical and non-interactive.

-
Do you have a specific setup in mind? $\:$ –  Ricky Demer Oct 31 '12 at 19:38
@SDL, I was thinking of $\textrm{commit}(x_2) = (g^{x_3}, x_2 h^{x_3})$, but I just now realized this might be problematic: this is binding for everyone, but not concealing against the person who holds the private key (the person who knows the discrete log of $h$ to base $g$ can infer what value was committed to without permission), which I suspect might not meet your needs. So, I withdraw my previous comment. Sorry for my error. –  D.W. Oct 31 '12 at 20:27
wait a minute: $\;\;$ How do you make sense of $\: x_2 \cdot \left(h^{x_1}\right) \:$ in a cyclic group? $\hspace{1.05 in}$ –  Ricky Demer Oct 31 '12 at 20:37
@D.W., I think it can work. At the end, it looks similar to Golle Universal Re-encryption construction, which is: (g^x1,x2⋅(h^x1),g^x3, h^x3). The difference is the "x2" multiplied in the fourth term. –  SDL Nov 1 '12 at 13:49
@RickyDemer: Ok, question corrected. –  SDL Nov 2 '12 at 16:21

As expressed, this is not possible. A zero-knowledge proof cannot be non-interactive. The reason is that any non-interactive proof can be forwarded to a third party who will accept it. This is excluded by standard definitions of zero-knowledge.

Could you rephrase you question and explain more precisely what you expect ?

EDIT

Seeing the comments and the fact that using Fiat-Shamir is OK, then an option is to write an interactive protocol with a moderate probability of catching a dishonest prover and then put several copies in parallel under Fiat-Shamir.

I propose the following protocol for the interactive part: Alice choose random values $(r_1,r_2)$ then she computes and sends to Bob for commitment the triple $(g^{r_1},r_2\cdot h^{r_1},h^{r_2})$.

Bob chooses at random to ask one of three different questions A, B or C.

• Case A: Send $r_1$, Bob check $g^{r_1}$ computes $r_2$ from the second part of the commitment triple and checks $h^{r_2}$.
• Case B: Alice sends $x_1-r_1$ (modulo in group order), $x_2/r_2$. Bob checks that $x_1-r_1$ is a log of $g^{x_1}/g^{r_1}$. From the second part of the commitment he computes $x_2\cdot h^{r_1}$ multiplying by $x_2/r_2$. From the public data he computes $x_2\cdot h^{x_1}/h^{x_1-r_1}$ which should be equal to the previous value.
• Case C: Alice sends $x_2-r_2$ and Bob checks that it is a log of $h^{x_2}/h^{r_2}$

This is a proof, because Alice cannot simultaneously answer the three questions without knowing $x_1$ and $x_2$. Moreover, if the triple is inconsistent, there exists no coherent answers to the three questions.

This is (computational) zero-knowledge, because if you know the question in advance, it is easy to prepare a commitment. Note that the zero-knowledge with this protocol is not going to be perfect or even statistical.

If this is not practical enough, you could try to refine this protocol along the line of Schnorr's signature scheme.

Additional EDIT I just saw in the comments that the case where someone knows the logarithm of $h$ in base $g$ might also be considered. This changes things quite a lot. In particular, if $h=g^z$, someone who knows $z$ can recover $x_2$ from the public data.

-
–  Ricky Demer Jul 6 at 19:12
In the random oracle model, there are standard constructions for non-interactive zero-knowledge proofs of knowledge. From the question, it is clear that the poster wants a proof of knowledge (not just a ZK proof). Since the person wants a practical solution, the random oracle model is a reasonable basis for seeking solutions. Therefore, the categorical statement that a "this is not possible" is not accurate. –  D.W. Jul 7 at 23:37
I do not consider a statement starting with "as expressed" and asking for a rephrased question to be categorical. I wanted to check whether the original poster was worrying or not about transferability. Still it might have been better to make that a comment rather than an answer. I can delete the answer. –  minar Jul 8 at 5:12
To clarify: Since the proof must be practical, I can accept a proof in ROM (using Fiat-Shamir heuristic, for example). I could even accept a proof of knowledge that is not zero knowledge. The key is that is must be practical, and secure regarding some standard security assumptions. Thanks. –  SDL Jul 8 at 13:07