# 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

Let $\#G$ denote the number of elements in the group. In your particular case, $\#G = \varphi{}(n)$ (and even $\#G = n-1$ if $n$ is prime). Let $\xleftarrow{\$}$denote a uniformly random sampling from a finite set of elements. Furthermore,$\mathbb{Z}_m$denotes the set of non-negative integers smaller than$m$and$\stackrel{?}{=}$denotes a equality test between two values to be performed by the Verifier. The Verifier accepts if and only if all such equalities hold. Public knowledge:$g, h, a, b, c$Claim: knowledge of$x_1, x_2$such that$(a,b,c) = (g^{x_1},x_2h^{x_1},h^{x_2})$Interactive proof:$\begin{matrix}Prover & & Verifier\\ v,s,s',s'' \xleftarrow{\$} \mathbb{Z}_{\#G} & & \\ & \xrightarrow{\begin{matrix}(g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v\end{matrix}} & & \\ & & k \xleftarrow{\$} \mathbb{Z}_{\#G} \\ & \xleftarrow{k} & \\ r \xleftarrow{} x_1 + ks \mod \#G & & \\ r' \xleftarrow{} x_2 + ks' \mod \#G & & \\ r'' \xleftarrow{} v + ks'' \mod \#G & & \\ & \xrightarrow{r,r',r''} & \\ & & g^r \stackrel{?}{=} a(g^s)^k \\ & & h^{r'} \stackrel{?}{=} c(h^{s'})^k \\ & & b^{r''} \stackrel{?}{=} ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v\end{matrix}$The proof can easily be made non-interactive by applying the Fiat-Shamir heuristic, i.e.:$k = \mathcal{H}(g,h,a,b,c,\ldots)$where$\mathcal{H}$is a suitable hash function which is applied to the input of the protocol and (optionally) some extra sources for randomness such as the time or the Prover's first message. Theorem 1. This interactive proof is complete, i.e.: if the claim is correct, the Verifier will accept. Proof. Proof by construction.$g^r = g^{x_1+ks} = a(g^{s})^kh^{r'} = g^{x_2+k{s'}} = c(h^{s'})^kb^{r''} = (x_2h^{x_1})^{r''} = (x_2h^{x_1})^{v + ks''} = ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v\square$Theorem 2. This interactive proof satisfies the special soundness property, i.e.: only if the claim is true will the Verifier accept (and, moreover, any two accepting transcripts of this proof applied to the same claim and starting with the same initial message will leak the witnesses$x_1$and$x_2$). Proof. We prove the "moreover" part of the theorem as it implies regular soundness. Given two transcripts$T_1$and$T_2$, we can first compute$s$from$T_1.r - T_2.r = (T_1.k - T_2.k)s$and then compute$x_1$. The same goes for$r', s'$and$x_2$. Of course, if$T_1.r = T_2.r$and$T_1.r' = T_2.r'$, then this does not leak the witnesses per se. However, in this case$T_1$can only be different from$T_2$if$T_1.r'' \ne T_2.r''$from which we can calculate$v$and$s''$. The latter value allows us to calculate the witness$x_2 = (x_2^{s''})^{s''^{-1}}$.$\square$Theorem 3. This interactive proof is special honest-verifier zero-knowledge. Proof. There exists a simulator algorithm$\mathcal{S}$which takes as input the claim$(g,h,a,b,c)$and a challenge$k$and outputs a transcript$S$of the interactive proof which is indistinguishable from the transcript$T$of an authentic interaction proving the same claim. The simulator$\mathcal{S}$generates a valid conversation$(((g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v),(k),(r,r',r''))$. Let the elements of this conversation represent variables which are to be assigned a definite value. The simulator$\mathcal{S}$does this as follows.$ \begin{matrix}r,r',r'' \xleftarrow{\$} \mathbb{Z}_{\#G} \\ v \xleftarrow{\$} \mathbb{Z}_{\#G} \\ (x_2h^{x_1})^v \xleftarrow{} b^v \\ (g^s) \xleftarrow{} (g^ra^{-1})^{k^{-1}} \\ (h^{s'}) \xleftarrow{} (h^{r'}c^{-1})^{k^{-1}} \\ (x_2^{s''}) \xleftarrow{\$} G \\ (h^{x_1s''}) \xleftarrow{} (b^{r''}b^{-v})^{k^{-1}}(x_2^{s''})^{-1} \end{matrix}$

There cannot exist a distinguisher $\mathcal{D}$ who can distinguish between an authentic transcript $T$ and a simulated transcript $S$. The distributions of $T$ and of $S$ are identical. $\square$

-
How does your reasoning for Theorem 2 work when the two transcripts have the same k? $\:$ (As far as I can see, that can only be the case when b is the identity element.) $\:$ Additionally, your reasoning for Theorem 3 $\hspace{.36 in}$ only shows honest-verifier zero-knowledge. $\:$ I believe it could easily be modified to show that the proof $\hspace{.39 in}$ is special honest-verifier zero knowledge, although that's not relevant to applying Fiat-Shamir. $\hspace{.75 in}$ –  Ricky Demer Dec 23 '13 at 22:15
Ricky Demer: In the proof of Theorem 2, we have two distinct authentic transcripts, meaning that both Prover and Verifier followed the protocol correctly. The selection of $k$ is the last probabilistic step. In other words, if the first claim is the same and the first message is the same, and if moreover $k$ is the same, then the last message must be the same also. –  Alan Sz Dec 24 '13 at 12:15
Ricky Demer: You're right, it only shows honest-verifier zero-knowledge. I changed that. Correct me if I'm wrong, but I thought that the word "special" in "special honest-verifier zero-knowledge" referred to the special soundness property (as opposed to regular soundness). I'll double-check. –  Alan Sz Dec 24 '13 at 12:19
Hmm, I guess I was wrong. An interactive proof is special honest-verifier zero-knowledge if the simulator $\mathcal{S}$ for a given claim and a given challenge. In the interactive proof proposed here, this is clearly the case. I'll change this. –  Alan Sz Dec 24 '13 at 12:28
Special soundness is something that must hold for cheating provers, otherwise it's far from useful. $\hspace{.5 in}$ I am assuming the verifier also checks that the 5-tuple it receives only contains elements of $G$ and that $\;\;\;\;$ the 3-tuple it receives only contains elements of $\hspace{.02 in}\{0,1,2,...,(\#G)-1\}$. $\:$ If that is the case, then additionally imposing the check "if $b=1$ then $r''=0$" would make a useful analogue of Theorem 2 true. $\:$ (However, that might break completeness; something that could be fixed by changing how the prover generates $r''$.) $\;\;\;$ –  Ricky Demer Dec 24 '13 at 19:42

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 '13 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 '13 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 '13 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 '13 at 13:07