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.
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 &amp; &amp; Verifier\\
v,s,s',s'' \xleftarrow{\$} \mathbb{Z}_{\#G} &amp; &amp; \\
 &amp; \xrightarrow{\begin{matrix}(g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v\end{matrix}} &amp; &amp; \\
&amp; &amp; k \xleftarrow{\$} \mathbb{Z}_{\#G} \\
&amp; \xleftarrow{k} &amp; \\
r \xleftarrow{} x_1 + ks \mod \#G &amp; &amp; \\
r' \xleftarrow{} x_2 + ks' \mod \#G &amp; &amp; \\
r'' \xleftarrow{} v + ks'' \mod \#G &amp; &amp; \\
&amp; \xrightarrow{r,r',r''} &amp; \\
&amp; &amp; g^r \stackrel{?}{=} a(g^s)^k \\
&amp; &amp; h^{r'} \stackrel{?}{=} c(h^{s'})^k \\
&amp; &amp; 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})^k$

$h^{r'} = g^{x_2+k{s'}} = c(h^{s'})^k$

$b^{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$